## Ramsey's Theorem

A generalization of Dilworth's Lemma. For each with , there exists a least Integer (the Ramsey Number) such that no matter how the Complete Graph is two-colored, it will contain a green Subgraph or a red Subgraph . Furthermore,

if . The theorem can be equivalently stated that, for all , there exists an such that any complete Digraph on Vertices contains a complete transitive Subgraph of Vertices. Ramsey's theorem is a generalization of the Pigeonhole Principle since

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