Ramsey's Theorem

A generalization of Dilworth's Lemma. For each $m, n \in \Bbb{N}$ with $m,n \geq 2$, there exists a least Integer $R(m,n)$ (the Ramsey Number) such that no matter how the Complete Graph $K_{R(m,n)}$ is two-colored, it will contain a green Subgraph $K_m$ or a red Subgraph $K_n$. Furthermore,

$$R(m,n)\leq R(m-1,n)+R(m,n-1)$$

if $m,n\geq 3$. The theorem can be equivalently stated that, for all $m\in \Bbb{N}$, there exists an $n\in \Bbb{N}$ such that any complete Digraph on $n$ Vertices contains a complete transitive Subgraph of $m$ Vertices. Ramsey's theorem is a generalization of the Pigeonhole Principle since

$$R(\underbrace{2, 2, \ldots, 2}_t) = t+1.$$

See also Dilworth's Lemma, Natural Independence Phenomenon, Pigeonhole Principle, Ramsey Number

References

Graham, R. L.; Rothschild, B. L.; and Spencer, J. H. Ramsey Theory, 2nd ed. New York: Wiley, 1990.

Spencer, J. ``Large Numbers and Unprovable Theorems.'' Amer. Math. Monthly 90, 669-675, 1983.