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

**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.

© 1996-9

1999-05-25