![]() ![]() ![]() ![]() |
![]() ![]() ![]() ![]() |
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,
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.