Ramsey's Theorem

Ramsey's Theorem is a fundamental result in combinatorics and graph theory that formalizes the idea that complete disorder is impossible. It guarantees that sufficiently large structures always contain a well-organized substructure.

Statement

For any positive integers $r, s$ , there exists a least positive integer $R(r, s)$ such that any simple graph with at least $R(r, s)$ vertices contains either:

a clique (complete subgraph) of size $r$ , or
an independent set (edgeless subgraph) of size $s$ .

This can also be interpreted in terms of edge colorings: In any coloring of the edges of a complete graph on $R(r, s)$ vertices using two colors (say, red and blue), there is either a red clique of size $r$ or a blue clique of size $s$ .

This result is often written as: $R(r, s) \rightarrow (r, s)$

Examples

$R(3, 3) = 6$ : In any two-coloring of the edges of $K_6$ , there is a monochromatic triangle. However, $R(3, 3) > 5$ , since there exists a two-coloring of $K_5$ with no monochromatic triangle.
$R(4, 4) = 18$ : Any red/blue coloring of the edges of $K_{18}$ must contain a red $K_4$ or a blue $K_4$ .

Exact values of Ramsey numbers are known only for small cases, and computing them is notoriously difficult.

Proof

A proof of Ramsey's Theorem proceeds by mathematical induction on the integers $r$ and $s$ . The key idea is to show that if the result holds for smaller values of $r$ and $s$ , then it also holds for larger values.

Base cases:

$R(1, s) = R(r, 1) = 1$ for all $r, s$ , since any graph with one vertex trivially contains either a clique of size 1 or an independent set of size 1.

Inductive step: Assume that $R(r - 1, s)$ and $R(r, s - 1)$ exist. Define: $R(r, s) \le R(r - 1, s) + R(r, s - 1)$

To prove this, consider any red/blue edge-coloring of the complete graph $K_n$ on $n = R(r - 1, s) + R(r, s - 1)$ vertices. Fix a vertex $v$ . Partition the remaining $n - 1$ vertices into two sets:

Let $A$ be the set of vertices joined to $v$ by a red edge.
Let $B$ be the set of vertices joined to $v$ by a blue edge.

By the pigeonhole principle, either $|A| \ge R(r - 1, s)$ or $|B| \ge R(r, s - 1)$ .

- If $|A| \ge R(r - 1, s)$ , then the subgraph induced by $A$ contains either:

A red $K_{r - 1}$ , which together with $v$ forms a red $K_r$ , or
A blue $K_s$ , which satisfies the theorem.

- If $|B| \ge R(r, s - 1)$ , then the subgraph induced by $B$ contains either:

A red $K_r$ , or
A blue $K_{s - 1}$ , which together with $v$ forms a blue $K_s$ .

Thus, in all cases, the coloring of $K_n$ contains either a red $K_r$ or a blue $K_s$ .

This completes the inductive step and proves that such a number $R(r, s)$ exists for all positive integers $r$ and $s$ .

Generalizations

Ramsey's Theorem has many generalizations:

For more than two colors
For hypergraphs instead of graphs
For infinite sets (Infinite Ramsey Theorem)

The infinite version states: For any coloring of the $k$ -element subsets of an infinite set into finitely many colors, there exists an infinite subset all of whose $k$ -element subsets are the same color.

Applications

Ramsey's Theorem has applications in:

Graph theory
Logic and theoretical computer science
Combinatorics and discrete mathematics
Olympiad problem solving, particularly in coloring and extremal problems

Related Theorems

External Links

Page

Toolbox

Search

Ramsey's Theorem

Contents

Ramsey's Theorem

Statement

Examples

Proof

Generalizations

Applications

Related Theorems

External Links