François G. Dorais

Research in Logic and Foundations of Mathematics

A partition theorem for finite trees

In a recent paper (Dorais–Gubkin–McDonald–Rivera 2013), Steven Gubkin, Daniel McDonald, Manuel Rivera, and I stumbled across what appears to be a new result in Ramsey theory. As the title of our paper suggests, this result was not exactly our main goal. Nevertheless, the result is very interesting so I feel it is a good idea to give it some extra publicity by writing about it here. I will only talk about a special case of our result (the case of Corollary 5.5 where the tree presentation has no sum nodes) and I will present it in a slightly different light. Our proof is somewhat convoluted, one could even say that the result is an accidental byproduct of the main result of the paper on automorphism groups of countably categorical linear orders. Because of this, I don’t feel like I understand how our result fits in the spectrum of known results in Ramsey theory. It is my hope that some of you may be able to fill-in some of the missing links…

Our new partition theorem is about (finite) ordered rooted trees. There are unfortunately several definitions needed to conveniently state our result. Recall that a rooted tree is a connected acyclic graph with a distinguished vertex, the root of the tree. For every node in a tree there is a unique path leading from to the root. If is not the root, the next node along this path is the parent of the other nodes adjacent to are the child nodes of these are the nodes that is the parent of. The root is the only node without a parent; node with no children is called a leaf node.

A homomorphism from a rooted tree to a rooted tree is a map from nodes of to nodes of that preserves the root and the child-parent relationship. So must send the root of to the root of and if is the parent of in then must be the parent of in Note that does not need to be one-to-one: two children of in could be mapped to the same child of in

A rooted tree can be lexicographically ordered by choosing a linear ordering on the children of each node. This induces a linear ordering of all nodes as follows: when is on the path leading from to the root of or where and are the nodes along the paths leading from and to the root immediately before their greatest common ancestor (note that and are both children of this common ancestor so we can compare them). It is easy to check that this is indeed a linear ordering of the nodes of What will be important to us is that this induces a linear ordering of the set of leaves of and that the set of all leaves that descend from a node of form an interval of An ordered rooted tree is a rooted tree together with a lexicographic ordering.

Fix a rooted tree An ordered -tree is an ordered rooted tree together with a homomorphism with the property that maps leaves of to leaves of In other words, if has a child in then must also have a child in If and are ordered -trees then is the set of all ordered -subtrees of that are isomorphic to (an isomorphism between ordered -trees is required to preserve the root, the child-parent relation, the lexicographic ordering, as well as the homomorphism to the rooted tree ). Let be ordered -trees and let be a positive integer, the partition relation means that:

For every coloring there are a color and a such that for all

Note that if we were dealing with plain sets instead of -trees and denoted all subsets of that are isomorphic to (i.e., have the same size as ) then the above is exactly as in the statement of Ramsey’s theorem.

We are now ready to state our partition theorem for finite ordered rooted trees.

Theorem. Let be a rooted tree. For all ordered -trees and every positive integer there is a -tree such that

This result is particularly versatile. It implies some interesting results in Ramsey theory, though that can only be seen by coding certain structures into -trees for some appropriate choice of

Ramsey’s theorem (Ramsey 1930) is one of the consequences of our partition theorem. Let be the rooted tree with two nodes — the root and one leaf. A -tree is simply an ordered tree with a distinguished root and a certain number of leaves. Say and are -trees with and leaves, respectively. Then an element of consists of a selection of leaves of together with the root of In other words, if we forget about the root, consists of all element subsets of a set of size — the set of leaves of So, if we completely forget about the tree structure, the theorem simply says that for all positive integers and there is a positive integer such that if the -element subsets of a set of size are colored with colors, then there is a subset of size all of whose -element subsets are colored the same way. This is exactly the statement of Ramsey’s theorem!

The case where consists of three nodes — the root, one leaf, and one intermediate node — was also considered by Rado (1954), see also Corollary 6.8 of (Kechris–Pestov–Todorcevic 2005). A -tree is an ordered tree all of whose leaves are at distance from the root. Again, the leaves of form a set of size say. The intermediate nodes of impose some additional structure on this set, namely they determine a partition where each part corresponds to the children of some intermediate node and the parts are ordered according to the ordering of Thus, the structure of can be described by the sequence of positive integers, where is the number of children of the -th intermediate node. Note that Suppose is similarly described by the sequence and set Forgetting about the tree structure, consists of all -element subsets of the partitioned set such that the first elements of belong to the same part of the next elements of belong to a later part of and so on. This determines a corresponding ordered partition of into parts, where the -th part has size When then the parts must match exactly and we recover some of the partition results for systems of sets that Rado considered in (Rado 1954).

Nguyen Van Thé (2009) has found a very clever way to talk about partitioned sets as above and even more general systems of nested partitions. Nguyen Van Thé’s convexly ordered ultrametric spaces correspond to the special case of the theorem where has a root, one leaf, and a certain number of intermediate nodes. Recall that an ultrametric space is a metric space where the distance satisfies the ultrametric inequality for all The balls of radius then form a partition of into a certain number of parts. If is moreover endowed with a linear order where each ball is an interval, then is a convexly ordered ultrametric space.

A finite convexly ordered ultrametric space whose distance function only takes values in the set corresponds to a -tree as follows. The -th level of consists of all balls

these are the nodes of that get mapped by the -tree homomorphism to the -th node of where the root is numbered and the leaf is numbered The edge relation on is given by the inclusion relation among these balls; so the node corresponding is always a child of that which corresponds to for Since balls of the same level are disjoint intervals of this induces a lexicographic ordering of the -tree Since the balls of radius are singletons, there is an obvious bijection between and the leaves of The distance can be read from the -tree by figuring the level of the greatest common ancestor of two leaf nodes of The correspondence just described also works backwards, from -trees to finite convexly ordered ultrametric spaces with distances in Our theorem for -trees thus corresponds exactly to Nguyen Van Thé’s partition theorem for this class of ultrametric spaces. Note that Nguyen Van Thé also considered more general sets of distances (including infinite sets) and he proves that these also have the Ramsey property; the infinite case is not a special case of our theorem but finite sets of distances behave exactly like for some

We have not found existing results that correspond to cases where is a branching rooted tree. It would be interesting to find more, but there is actually a more pressing matter that stems from our unusual proof. Our proof goes through a wonderful result of Kechris, Pestov and Todorcevic (2005) that ties structural Ramsey results with topological dynamics and model theory. Basically, we computed the automorphism groups of countably categorical linear orders with additional structure and found that these groups have the right dynamical properties to apply the results of Kechris, Pestov and Todorcevic. In particular, there is no known combinatorial proof of our partition theorem for -trees! It would be very interesting to find one, especially one that would relate our result to some classical results in Ramsey theory…

References

  1. F. G. Dorais, S. Gubkin, D. McDonald, M. Rivera, 2013: Automorphism groups of countably categorical linear orders are extremely amenable, Order 30, 415–426.

  2. A. S. Kechris, V. G. Pestov, S. Todorcevic, 2005: Fraïssé limits, Ramsey theory, and topological dynamics, Geom. Funct. Anal. 15, no. 1, 106–189.

  3. L. Nguyen Van Thé, 2009: Ramsey degrees of finite ultrametric spaces, ultrametric Urysohn spaces and dynamics of their isometry groups, European J. Combin. 30, no. 4, 934–945.

  4. R. Rado, 1954: Direct decomposition of partitions, J. London Math. Soc. 29, 71–83.

  5. F. P. Ramsey, 1930: On a problem of formal logic, Proc. London Math. Soc. (2) 30, 264–286.

CC0 Originally posted on by François G. Dorais. To the extent possible under law, François G. Dorais has waived all copyright and neigboring rights to this work.