TOPICS

# Ramsey's Theorem

Ramsey's theorem is a generalization of Dilworth's lemma which states for each pair of positive integers and there exists an integer (known as the Ramsey number) such that any graph with nodes contains a clique with at least nodes or an independent set with at least nodes.

Another statement of the theorem is that for integers , there exists a least positive integer such that no matter how the complete graph is two-colored, it will contain a green subgraph or a red subgraph .

A third statement of the theorem states that for all , there exists an such that any complete digraph on graph vertices contains a complete vertex-transitive subgraph of graph vertices.

For example, and , but are only known to lie in the ranges and .

It is true that

if .

Dilworth's Lemma, Dirichlet's Box Principle, Extremal Graph Theory, Graph Coloring, Natural Independence Phenomenon, Party Problem, Ramsey Number, Ramsey Theory

## Explore with Wolfram|Alpha

More things to try:

## References

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 33-34, 2003.Graham, R. L.; Rothschild, B. L.; and Spencer, J. H. Ramsey Theory, 2nd ed. New York: Wiley, 1990.Mileti, J. "Ramsey's Theorem." http://www.math.uiuc.edu/~mileti/Museum/ramsey.html.Spencer, J. "Large Numbers and Unprovable Theorems." Amer. Math. Monthly 90, 669-675, 1983.

Ramsey's Theorem

## Cite this as:

Weisstein, Eric W. "Ramsey's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RamseysTheorem.html