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
2011729349 2025590344 2545825365 1560716145
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 . We consider the following problem. Given a rooted tree @math , label the nodes of @math in the most compact way such that, given the labels of two nodes @math and @math , one can determine in constant time, by looking only at the labels, whether @math is ancestor of @math . The best known labeling scheme is rather straightforward and uses labels of length at most @math bits each, where @math is the number of nodes in the tree. Our main result in this paper is a labeling scheme with maximum label length @math . Our motivation for studying this problem is enhancing the performance of web search engines. In the context of this application each indexed document is a tree, and the labels of all trees are maintained in main memory. Therefore even small improvements in the maximum label length are important. Consider a uniform random rooted tree on vertices labelled by @math , with edges directed towards the root. We imagine that each node of the tree has space for a single car to park. A number @math of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path oriented towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider @math and let @math denote the event that all @math cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if @math , we have @math , whereas if @math we have @math . We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we are led to consider the following variant of the problem: take the tree to be the family tree of a Galton-Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson( @math ) number of cars arrive at each vertex. Let @math be the number of cars which visit the root of the tree. Then for @math , we have @math , whereas for @math , we have @math . This discontinuous phase transition turns out to be a generic phenomenon in settings with an arbitrary offspring distribution of mean at least 1 for the tree and arbitrary arrival distribution. We present a labeling scheme for rooted trees which allows to compute, from the label of v alone, unique identifiers for the ancestors of v that are at distance at most d from v. For any constant d our labeling scheme produce labels of length log n+O(√log n), and for d ∈ O(√log n) the labels are still of length O(log n). In particular, given the labels of two nodes u and v we can determine from the labels alone whether u is the parent of v or vice versa, whether u and v are siblings, and whether u and v are at distance at most d from each other. The need for such labeling scheme arises in several application areas, including in particular communication networks and search engines for large collections ofWeb XML files. In the latter application XML files are viewed as trees, and typical queries ask for XML files containing a particular set of nodes with specific ancestor, parent, or sibling relationships among them.