In
mathematics, the Milliken–Taylor theorem in
combinatorics is a generalization of both
Ramsey's theorem
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say ...
and
Hindman's theorem. It is named after Keith Milliken and
Alan D. Taylor
Alan Dana Taylor (born October 27, 1947) is an American mathematician who, with Steven Brams, solved the problem of envy-free cake-cutting for an arbitrary number of people with the Brams–Taylor procedure.
Taylor received his Ph.D. in 1975 f ...
.
Let
denote the set of finite subsets of
, and define a partial order on
by α<β
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is b ...
max α
\langle a_n \rangle_^\infty \subset \mathbb and , let
:
Let denote the ''k''-element subsets of a set ''S''. The Milliken–Taylor theorem says that for any finite partition , there exist some and a sequence such that .
For each , call an ''MTk set''. Then, alternatively, the Milliken–Taylor theorem asserts that the collection of MT''k'' sets is partition regular for each ''k''.
References
*.
*.
Ramsey theory
Theorems in discrete mathematics
{{combin-stub