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 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 then for some strongly embedded infinite subtree R of T, S R n ⊂ 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 where T ranges over finitely splitting rooted trees of height ω. Milliken's tree theorem says that not only is S n partition regular for each n < ω, but that the homogeneous subtree R guaranteed by the theorem is strongly embedded in T.
Call T an α-tree if each branch of T has cardinality α. Define Succ(p, P)= { q ∈ P : q ≥ p } , and I S ( 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 , and the partial order on S is induced from T,if s ∈ S is nonmaximal in S and t ∈ I S ( s , T ) , then | S u c c ( t , T ) ∩ I S ( s , S ) | = 1 ,there exists a strictly increasing function from α to β , such that S ( n ) ⊂ T ( f ( n ) ) . Intuitively, for S to be strongly embedded in T,
S must be a subset of T with the induced partial orderS 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 SS preserves the level structure of T; all nodes on a common level of S must be on a common level in T.