Ramsey's Theorem

Ramsey's theorem is the foundational result of Ramsey theory, guaranteeing that complete disorder is impossible in sufficiently large structures. We state and discuss both the finite and infinite versions.

Statement

Theorem5.1Ramsey's Theorem (Finite Version)

For all positive integers $k, r, n_1, n_2, \ldots, n_r$ , there exists a positive integer $N = R_k(n_1, \ldots, n_r)$ such that the following holds: for every $r$ -coloring of $\binom{[N]}{k}$ , there exists an index $i \in \{1, \ldots, r\}$ and a subset $S \subseteq [N]$ with $|S| = n_i$ such that all $k$ -element subsets of $S$ receive color $i$ .

Theorem5.2Ramsey's Theorem (Infinite Version)

For every $r$ -coloring of $\binom{\mathbb{N}}{k}$ , there exists an infinite subset $S \subseteq \mathbb{N}$ such that $\binom{S}{k}$ is monochromatic.

Proof Sketch for the Graph Case

Proof

We prove $R(s, t) < \infty$ by induction. The base cases $R(1, t) = 1$ and $R(s, 1) = 1$ are trivial.

For the inductive step, we claim $R(s, t) \leq R(s-1, t) + R(s, t-1)$ . Let $N = R(s-1, t) + R(s, t-1)$ and consider a 2-coloring (red/blue) of $E(K_N)$ . Pick any vertex $v$ . Let $A$ be the set of vertices connected to $v$ by red edges, and $B$ those by blue edges. Then $|A| + |B| = N - 1 \geq R(s-1, t) + R(s, t-1) - 1$ , so either $|A| \geq R(s-1, t)$ or $|B| \geq R(s, t-1)$ .

Case 1: $|A| \geq R(s-1, t)$ . By the definition of $R(s-1, t)$ , the subgraph induced on $A$ contains either a red $K_{s-1}$ (which, together with $v$ , gives a red $K_s$ ) or a blue $K_t$ .

Case 2: $|B| \geq R(s, t-1)$ . Symmetrically, $B$ contains a red $K_s$ or a blue $K_{t-1}$ (giving, with $v$ , a blue $K_t$ ).

In all cases, we find a red $K_s$ or a blue $K_t$ . The bound $R(s,t) \leq \binom{s+t-2}{s-1}$ follows by induction and Pascal's identity. $\square$

■

Applications

ExampleParty Problem

$R(3,3) = 6$ : Among any 6 people, there exist 3 mutual acquaintances or 3 mutual strangers. To see $R(3,3) \geq 6$ , color the edges of $K_5$ with a red $C_5$ and blue $C_5$ ; neither contains a monochromatic triangle.

RemarkConstructive vs. Existential Bounds

The proof of Ramsey's theorem is inherently non-constructive for large parameters. No explicit construction is known that achieves $R(n, n) \geq c^n$ for any $c > \sqrt{2}$ . The probabilistic method gives $R(n,n) \geq (1+o(1))\frac{n}{e\sqrt{2}} \cdot 2^{n/2}$ , but this is also non-constructive.