Milliken–Taylor theorem

In mathematics, the Milliken–Taylor theorem in combinatorics is a generalization of both Ramsey's theorem and Hindman's theorem. It is named after Keith Milliken and Alan D. Taylor.

Let $\mathcal{P}_f(\mathbb{N})$ denote the set of finite subsets of $\mathbb{N}$, and define a partial order on $\mathcal{P}_f(\mathbb{N})$ by α<β if and only if max α<min β. Given a sequence of integers $\langle a_n \rangle_{n=0}^\infty \subset \mathbb{N}$ and k > 0, let

$[FS(\langle a_n \rangle_{n=0}^\infty)]^k_< = \left \{ \left \{ \sum \alpha_1, \ldots , \sum \alpha_k \right \}: \alpha_1 ,\cdots , \alpha_k \in \mathcal{P}_f(\mathbb{N})\text{ and }\alpha_1 <\cdots < \alpha_k \right \}.$

Let $[S]^k$ denote the k-element subsets of a set S. The Milliken–Taylor theorem says that for any finite partition $[\mathbb{N}]^k=C_1 \cup C_2 \cup \cdots \cup C_r$, there exist some i ≤ r and a sequence $\langle a_n \rangle_{n=0}^{\infty} \subset \mathbb{N}$ such that $[FS(\langle a_n \rangle_{n=0}^{\infty})]^k_< \subset C_i$.

For each $\langle a_n \rangle_{n=0}^\infty \subset \mathbb{N}$, call $[FS(\langle a_n \rangle_{n=0}^\infty)]^k_<$ an MT^k set. Then, alternatively, the Milliken–Taylor theorem asserts that the collection of MT^k sets is partition regular for each k.

References

• Milliken, Keith R. (1975), "Ramsey's theorem with sums or unions", Journal of Combinatorial Theory, Series A 18: 276–290, doi:10.1016/0097-3165(75)90039-4, MR 0373906.
• Taylor, Alan D. (1976), "A canonical partition relation for finite subsets of ω", Journal of Combinatorial Theory, Series A 21 (2): 137–146, doi:10.1016/0097-3165(76)90058-3, MR 0424571.