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 P f ( N ) {\displaystyle {\mathcal {P}}_{f}(\mathbb {N} )} denote the set of finite subsets of N {\displaystyle \mathbb {N} } , and define a partial order on P f ( N ) {\displaystyle {\mathcal {P}}_{f}(\mathbb {N} )} by α<β if and only if max α<min β. Given a sequence of integers ⟨ a n ⟩ n = 0 ∞ ⊂ N {\displaystyle \langle a_{n}\rangle _{n=0}^{\infty }\subset \mathbb {N} } and k > 0, let
[ F S ( ⟨ a n ⟩ n = 0 ∞ ) ] < k = { { ∑ t ∈ α 1 a t , … , ∑ t ∈ α k a t } : α 1 , ⋯ , α k ∈ P f ( N ) and α 1 < ⋯ < α k } . {\displaystyle [FS(\langle a_{n}\rangle _{n=0}^{\infty })]_{<}^{k}=\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}<\cdots <\alpha _{k}\right\}.}
Let [ S ] k {\displaystyle [S]^{k}} denote the k-element subsets of a set S. The Milliken–Taylor theorem says that for any finite partition [ N ] k = C 1 ∪ C 2 ∪ ⋯ ∪ C r {\displaystyle [\mathbb {N} ]^{k}=C_{1}\cup C_{2}\cup \cdots \cup C_{r}} , there exist some i ≤ r and a sequence ⟨ a n ⟩ n = 0 ∞ ⊂ N {\displaystyle \langle a_{n}\rangle _{n=0}^{\infty }\subset \mathbb {N} } such that [ F S ( ⟨ a n ⟩ n = 0 ∞ ) ] < k ⊂ C i {\displaystyle [FS(\langle a_{n}\rangle _{n=0}^{\infty })]_{<}^{k}\subset C_{i}} . For each ⟨ a n ⟩ n = 0 ∞ ⊂ N {\displaystyle \langle a_{n}\rangle _{n=0}^{\infty }\subset \mathbb {N} } , call [ F S ( ⟨ a n ⟩ n = 0 ∞ ) ] < k {\displaystyle [FS(\langle a_{n}\rangle _{n=0}^{\infty })]_{<}^{k}} 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, 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.