Misplaced Pages

Milliken's tree theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Theorem in combinatorics generalizing Ramsey's theorem to infinite trees
This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources.
Find sources: "Milliken's tree theorem" – news · newspapers · books · scholar · JSTOR (July 2022) (Learn how and when to remove this message)

In mathematics, Milliken's tree theorem in combinatorics is a partition theorem generalizing Ramsey's theorem to infinite trees, objects with more structure than sets.

Let T be a finitely splitting rooted tree of height ω, n a positive integer, and S T n {\displaystyle \mathbb {S} _{T}^{n}} the collection of all strongly embedded subtrees of T of height n. In one of its simple forms, Milliken's tree theorem states that if S T n = C 1 ∪ . . . ∪ C r {\displaystyle \mathbb {S} _{T}^{n}=C_{1}\cup ...\cup C_{r}} then for some strongly embedded infinite subtree R of T, S R n ⊂ C i {\displaystyle \mathbb {S} _{R}^{n}\subset C_{i}} for some i ≤ r.

This immediately implies Ramsey's theorem; take the tree T to be a linear ordering on ω vertices.

Define S n = ⋃ T S T n {\displaystyle \mathbb {S} ^{n}=\bigcup _{T}\mathbb {S} _{T}^{n}} where T ranges over finitely splitting rooted trees of height ω. Milliken's tree theorem says that not only is S n {\displaystyle \mathbb {S} ^{n}} partition regular for each n < ω, but that the homogeneous subtree R guaranteed by the theorem is strongly embedded in T.

Strong embedding

Call T an α-tree if each branch of T has cardinality α. Define Succ(p, P)= { q ∈ P : q ≥ p } {\displaystyle \{q\in P:q\geq p\}} , and I S ( p , P ) {\displaystyle IS(p,P)} to be the set of immediate successors of p in P. Suppose S is an α-tree and T is a β-tree, with 0 ≤ α ≤ β ≤ ω. S is strongly embedded in T if:

  • S ⊂ T {\displaystyle S\subset T} , and the partial order on S is induced from T,
  • if s ∈ S {\displaystyle s\in S} is nonmaximal in S and t ∈ I S ( s , T ) {\displaystyle t\in IS(s,T)} , then | S u c c ( t , T ) ∩ I S ( s , S ) | = 1 {\displaystyle |Succ(t,T)\cap IS(s,S)|=1} ,
  • there exists a strictly increasing function from α {\displaystyle \alpha } to β {\displaystyle \beta } , such that S ( n ) ⊂ T ( f ( n ) ) . {\displaystyle S(n)\subset T(f(n)).}

Intuitively, for S to be strongly embedded in T,

  • S must be a subset of T with the induced partial order
  • S must preserve the branching structure of T; i.e., if a nonmaximal node in S has n immediate successors in T, then it has n immediate successors in S
  • S preserves the level structure of T; all nodes on a common level of S must be on a common level in T.

References

  1. Keith R. Milliken, A Ramsey Theorem for Trees J. Comb. Theory (Series A) 26 (1979), 215-237
  2. Keith R. Milliken, A Partition Theorem for the Infinite Subtrees of a Tree, Trans. Amer. Math. Soc. 263 No.1 (1981), 137-148.
Categories: