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 .

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength