Combinatorics and discrete mathematics

Ramsey theory

Shows that complete disorder is impossible: any large enough structure must contain an orderly pattern.

IntuitionThe party of six: strangers and mutual friends

Invite any $6$ people to a party. Between each pair, either they have met before (draw a red edge) or they are strangers (draw a blue edge). No matter how the $15$ relationships are arranged, there will always be either $3$ people who all know each other (a red triangle $K_3$ ) or $3$ people who are all mutual strangers (a blue triangle $K_3$ ). With $5$ people it is possible to avoid both, so $R(3,3) = 6$ is the exact threshold where order is forced out of chaos.

In a complete graph

K_6

, any vertex

v

has

5

incident edges in

2

colors; by the pigeonhole principle at least

3

share a color, forcing a monochromatic

K_3

UndergraduateRamsey numbers and the Erdős–Szekeres recursion

Definition: Two-color Ramsey number R(s, t)

For integers $s, t \ge 2$ , the Ramsey number $R(s, t)$ is the smallest integer $N$ such that every red–blue coloring of the edges of the complete graph $K_N$ contains either a red complete subgraph $K_s$ or a blue complete subgraph $K_t$ .

R(s, t) \le R(s - 1, t) + R(s, t - 1) \le \binom{s + t - 2}{s - 1}

2^{k/2} < R(k, k) \le \binom{2k - 2}{k - 1} < 4^{k - 1}

Exactly known small two-color Ramsey numbers R(s, t)
Pair $(s, t)$	Exact value or best known range	Landmark
$R(3, 3)$	$6$	Putnam 1953
$R(3, 4)$	$9$	Greenwood–Gleason 1955
$R(4, 4)$	$18$	Greenwood–Gleason 1955
$R(5, 5)$	$43 \le R(5, 5) \le 46$	Open (Angeltveit–McKay 2024)

UndergraduateCore theorems and proofs

Theorem: Exact evaluation R(3, 3) = 6

The Ramsey number $R(3, 3)$ equals $6$ : every $2$ -coloring of the edges of $K_6$ contains a monochromatic $K_3$ , while $K_5$ admits a coloring with no monochromatic $K_3$ .

Why is it true?

A single vertex in $K_6$ has $5$ neighbors; splitting them into $2$ colors puts at least $3$ in the same class, and whether those $3$ have an edge of that color among themselves or not, a monochromatic triangle appears.

Proof

**Step 1 (upper bound $R(3,3) \le 6$ ).** Pick any vertex $v$ of $K_6$ . Its $5$ incident edges are colored red or blue. By the pigeonhole principle ( $\lceil 5/2 \rceil = 3$ ), at least $3$ of these edges have the same color — say edges $vu_1, vu_2, vu_3$ are all red.

**Step 2 (case split on $\{u_1, u_2, u_3\}$ ).** Look at the $3$ edges inside the triangle $\{u_1, u_2, u_3\}$ . If any one of them — say $u_1u_2$ — is red, then $\{v, u_1, u_2\}$ is a red $K_3$ . Otherwise all $3$ edges $u_1u_2, u_2u_3, u_3u_1$ are blue, so $\{u_1, u_2, u_3\}$ itself is a blue $K_3$ .

**Step 3 (lower bound $R(3,3) > 5$ ).** Label the vertices of $K_5$ by $\mathbb{Z}/5\mathbb{Z}$ . Color edge $ij$ red if $i - j \equiv \pm 1 \pmod 5$ and blue if $i - j \equiv \pm 2 \pmod 5$ . Both color classes form a $5$ -cycle, triangle-free, proving $R(3,3) > 5$ and hence $R(3,3) = 6$ .

Theorem: Erdős–Szekeres upper bound for Ramsey numbers

For all integers $s, t \ge 2$ , the Ramsey number $R(s, t)$ is finite and satisfies $R(s, t) \le R(s - 1, t) + R(s, t - 1)$ . Consequently, $R(s, t) \le \binom{s + t - 2}{s - 1}$ .

Why is it true?

Fix a vertex $v$ : either its red neighborhood is large enough to force a red $K_{s-1}$ or a blue $K_t$ , or else its blue neighborhood is large enough to force a red $K_s$ or a blue $K_{t-1}$ .

Proof

**Step 1 (pigeonhole split of the neighborhood of $v$ ).** Let $N = R(s - 1, t) + R(s, t - 1)$ and fix a vertex $v \in V(K_N)$ . Partition the remaining $N - 1$ vertices into $V_R$ (red edge to $v$ ) and $V_B$ (blue edge to $v$ ). Since $|V_R| + |V_B| = R(s - 1, t) + R(s, t - 1) - 1$ , either $|V_R| \ge R(s - 1, t)$ or $|V_B| \ge R(s, t - 1)$ .

Step 2 (inductive conclusion). If $|V_R| \ge R(s - 1, t)$ , the subgraph on $V_R$ contains a blue $K_t$ or a red $K_{s-1}$ that joins $v$ to form a red $K_s$ . Symmetrically for $V_B$ .

Step 3 (binomial bound by induction). Base cases $R(2, t) = t$ and $R(s, 2) = s$ match $\binom{t}{1}$ and $\binom{s}{s-1}$ . For $s, t \ge 3$ , Pascal's identity gives $R(s, t) \le \binom{s + t - 3}{s - 2} + \binom{s + t - 3}{s - 1} = \binom{s + t - 2}{s - 1}$ .

AdvancedApplications and Worked Examples

Ramsey theory underpins communications network design, theoretical computer science (lower bounds via Dickson's lemma and Kruskal's tree theorem), and additive combinatorics (Schur's theorem and van der Waerden's theorem on monochromatic arithmetic progressions).

Example: Proving R(3, 4) = 9 using degree parity

The Erdős–Szekeres recursion gives $R(3, 4) \le R(2, 4) + R(3, 3) = 4 + 6 = 10$ . Improve this to $R(3, 4) \le 9$ using the parity of red degrees in $K_9$ .

Solution

In any coloring of $K_9$ , if some vertex $v$ has red degree $d_R(v) \ge 4$ , its $4$ red neighbors either contain a red edge (forming a red $K_3$ with $v$ ) or all blue edges between them (forming a blue $K_4$ ). If some vertex has $d_R(v) \le 2$ , its blue degree $d_B(v) = 8 - d_R(v) \ge 6 = R(3, 3)$ , so its blue neighborhood contains a red or blue $K_3$ .

The only remaining case is $d_R(v) = 3$ for every vertex. But the degree sum $\sum_v d_R(v)$ must be even, whereas $9 \times 3 = 27$ is odd — impossible! Thus $R(3, 4) \le 9$ , and an explicit construction shows $R(3, 4) = 9$ .

Example: Three-color Ramsey number R(3, 3, 3) = 17

Show that if the edges of $K_{17}$ are colored with $3$ colors, there must be a monochromatic triangle $K_3$ .

Solution

Pick a vertex $v$ . Its $16$ incident edges are partitioned into $3$ classes, so at least one has $\ge \lceil 16/3 \rceil = 6$ edges. Suppose $v$ has $6$ green edges to a set $U$ .

If any edge inside $U$ is green, it joins $v$ to form a green $K_3$ . Otherwise, edges inside $U$ use only the remaining colors on $|U| = 6 = R(3, 3)$ vertices, forcing a monochromatic $K_3$ .

What is the exact value of the Ramsey number $R(3, 3)$ ?

What upper bound does $R(s, t) \le R(s-1,t) + R(s,t-1)$ give for $R(4, 4)$ , using $R(3,4) = 9$ ?

For any integer $k \ge 2$ , what is the exact value of $R(2, k)$ ?

What did the 2023 breakthrough of Campos, Griffiths, Morris, and Sahasrabudhe establish for $R(k, k)$ ?

References

Marcelo Campos, Simon Griffiths, Robert Morris, Julian Sahasrabudhe (2023). An exponential improvement for diagonal Ramsey · arXiv:2303.09521
Sam Mattheus, Jacques Verstraëte (2024). The asymptotics of r(4,t) · DOI:10.4007/annals.2024.199.2.8
Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer (1990). Ramsey Theory (2nd ed.)