Milliken–Taylor theorem

{{short description|Generalization of both Ramsey's theorem and Hindman's theorem}}

{{technical|date=December 2014}}

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 $\backslash mathcal\{P\}\_f(\backslash mathbb\{N\})$ denote the set of finite subsets of $\backslash mathbb\{N\}$, and define a partial order on $\backslash mathcal\{P\}\_f(\backslash mathbb\{N\})$ by α<β if and only if max α\langle a_n \rangle_{n=0}^\infty \subset \mathbb{N} and {{nowrap|k > 0}}, let

:

Let $[S]^k$ denote the k-element subsets of a set S. The Milliken–Taylor theorem says that for any finite partition $[\backslash mathbb\{N\}]^k=C\_1\; \backslash cup\; C\_2\; \backslash cup\; \backslash cdots\; \backslash cup\; C\_r$, there exist some {{nowrap|i ≤ r}} and a sequence $\backslash langle\; a\_n\; \backslash rangle\_\{n=0\}^\{\backslash infty\}\; \backslash subset\; \backslash mathbb\{N\}$ such that .

For each $\backslash langle\; a\_n\; \backslash rangle\_\{n=0\}^\backslash infty\; \backslash subset\; \backslash mathbb\{N\}$, call an MT^k set. Then, alternatively, the Milliken–Taylor theorem asserts that the collection of MT^k sets is partition regular for each k.