Ramsey's Theorem
A generalization of Dilworth's Lemma. For each 
with 
, there exists a leastInteger 
(the Ramsey Number) such that no matter how the Complete Graph 
istwo-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 thatany complete Digraph on 
Vertices contains a complete transitive Subgraph of 
Vertices. Ramsey's theorem is a generalization of the Pigeonhole Principle since
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.
- Dirichlet Kernel
- Dirichlet Lambda Function
- Dirichlet L-Series
- Dirichlet Region
- Dirichlet's Boxing-In Principle
- Dirichlet's Box Principle
- Dirichlet Series
- Dirichlet's Formula
- Dirichlet's Lemma
- Dirichlet's Principle
- Dirichlet's Test
- Dirichlet's Theorem
- Dirichlet Structure Constant
- Dirichlet Tessellation
- Dirty Beam
- Dirty Map
- Disc
- Disconnected Form
- Disconnectivity
- Discontinuity
- Discontinuous
- Discordant Permutation
- Discrepancy Theorem
- Discrete Distribution
- Discrete Fourier Transform