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 [math]\displaystyle{ \mathcal{P}_f(\mathbb{N}) }[/math] denote the set of finite subsets of [math]\displaystyle{ \mathbb{N} }[/math], and define a partial order on [math]\displaystyle{ \mathcal{P}_f(\mathbb{N}) }[/math] by α<β if and only if max α<min β. Given a sequence of integers [math]\displaystyle{ \langle a_n \rangle_{n=0}^\infty \subset \mathbb{N} }[/math] and k > 0, let
- [math]\displaystyle{ [FS(\langle a_n \rangle_{n=0}^\infty)]^k_\lt = \left \{ \left \{ \sum_{t\in \alpha_1}a_t, \ldots , \sum_{t\in \alpha_k}a_t \right \}: \alpha_1 ,\cdots , \alpha_k \in \mathcal{P}_f(\mathbb{N})\text{ and }\alpha_1 \lt \cdots \lt \alpha_k \right \}. }[/math]
Let [math]\displaystyle{ [S]^k }[/math] denote the k-element subsets of a set S. The Milliken–Taylor theorem says that for any finite partition [math]\displaystyle{ [\mathbb{N}]^k=C_1 \cup C_2 \cup \cdots \cup C_r }[/math], there exist some i ≤ r and a sequence [math]\displaystyle{ \langle a_n \rangle_{n=0}^{\infty} \subset \mathbb{N} }[/math] such that [math]\displaystyle{ [FS(\langle a_n \rangle_{n=0}^{\infty})]^k_\lt \subset C_i }[/math].
For each [math]\displaystyle{ \langle a_n \rangle_{n=0}^\infty \subset \mathbb{N} }[/math], call [math]\displaystyle{ [FS(\langle a_n \rangle_{n=0}^\infty)]^k_\lt }[/math] an MTk set. Then, alternatively, the Milliken–Taylor theorem asserts that the collection of MTk 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 (3): 276–290, doi:10.1016/0097-3165(75)90039-4.
- "A canonical partition relation for finite subsets of ω", Journal of Combinatorial Theory, Series A 21 (2): 137–146, 1976, doi:10.1016/0097-3165(76)90058-3.
 |  |
