We show that the class of finite rooted binary plane trees is a Ramsey class (with respect to topological embeddings that map leaves to leaves). That is, for all such trees P,H and every natural number k there exists a tree T such that for every k-coloring of the (topological) copies of P in T there exists a (topological) copy H' of H in T such that all copies of P in H' have the same color. When the trees are represented by the so-called rooted triple relation, the result gives rise to a Ramsey class of relational structures with respect to induced substructures.
The result presented here gives rise to a new Ramsey class, and hence contributes to the classification program. We have to describe how to represent rooted binary plane trees as relational structures. Our relational structures will be ordered, i.e., the signature contains a binary relation symbol @math that is interpreted by a linear order. The tree structure is represented by a single ternary relation symbol as follows. For leaves @math of a tree, we write @math if the least common ancestor of @math and @math is below the least common ancestor of @math and @math in the tree; the relation @math is also called the , following terminology in phylogenetic reconstruction @cite_14 @cite_15 @cite_7 . It is known that a rooted binary tree is described up to isomorphism by the rooted triple relation (see e.g. @cite_14 ).
@cite_15 @cite_14 @cite_7
2130775582 2075503802 2011729349
Abstract We give an algorithm for finding the set of all rooted trees with labelled leaves having subtrees homeomorphic to each of a given set of rooted trees with labelled leaves. This type of problem arises in the study of evolutionary trees. In taxonomy and other branches of classification it is useful to know when tree-like classifications on overlapping sets of labels can be consistently combined into a parent tree. This paper considers the computation complexity of this problem. Recognizing when a consistent parent tree exists is shown to be intractable (NP-complete) for sets of unrooted trees, even when each tree in the set classifies just four labels. Consequently determining the compatibility of qualitative characters and partial binary characters is, in general, also NP-complete. However for sets of rooted trees an algorithm is described which constructs the “strict consensus tree” of all consistent parent trees (when they exist) in polynomial time. The related question of recognizing when a set of subtrees uniquely defines a parent tree is also considered, and a simple necessary and sufficient condition is described for rooted trees. We are given a set ( T ) = T 1 ,T 2 , . . .,T k of rooted binary trees, each T i leaf-labeled by a subset ( L (T_i) 1,2, . . ., n ) . If T is a tree on 1,2, . . .,n , we let ( T| L ) denote the minimal subtree of T induced by the nodes of ( L ) and all their ancestors. The consensustreeproblem asks whether there exists a tree T * such that, for every i , ( T^* | L (T_i) ) is homeomorphic to T i .