40.05.04 · combinatorics / extremal-ramsey

Ramsey's Theorem and Ramsey Numbers

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §9.1-§9.4 (Ramsey's theorem, induced Ramsey, the canonical Ramsey theorem of Erdős-Rado); Graham-Rothschild-Spencer 1990 *Ramsey Theory* (2nd ed., Wiley) Ch. 1-7 (van der Waerden, Hales-Jewett, Rado's theorem, the canonical theorem); the original sources Ramsey 1930 (*Proc. London Math. Soc.*), Erdős-Szekeres 1935 (*Compositio Math.*), Erdős 1947 (*Bull. AMS*), Schur 1916, van der Waerden 1927, Hales-Jewett 1963, Szemerédi 1975

Intuition Beginner

Complete disorder is impossible. That is the slogan of Ramsey theory, and it sounds almost backwards. We expect that if you scatter things randomly they will look like a mess with no pattern. Ramsey's theorem says the opposite: once a structure is large enough, some neat pattern is forced to appear no matter how hard you try to avoid it. You cannot make everything random; a big enough system always hides an island of order.

The cleanest example is a party. Suppose six people are in a room. Take any two of them; either they already know each other or they are strangers. Colour each pair: a red line if the two are acquainted, a blue line if they are strangers. The surprising fact is that among any six people you can always find three who are mutual acquaintances (a red triangle) or three who are mutual strangers (a blue triangle). With only five people you can dodge it, but at six it becomes unavoidable. You do not get to pick the friendships; whatever they are, the pattern is already there.

The smallest size that forces the pattern is called a Ramsey number. Here it is six, written $R (3, 3) = 6$ : six people force a same-colour triangle. The numbers grow ferociously fast and become almost impossible to pin down exactly, which is part of what makes the subject so strange and so deep.

Visual Beginner

Picture five dots arranged in a ring, every pair joined by a line, and colour each line red or blue. With five dots you can be clever: draw the outer five-sided ring in red and the inner five-pointed star in blue. Now no three dots are joined by three lines of one colour. Five dots can escape.

Now add a sixth dot and look at it alone. It sends five lines out to the other five dots. Each line is red or blue, and five lines split into two colours, so one colour is used at least three times. Say three of its lines are red, reaching three other dots.

step	count	what it forces
lines from the sixth dot	5	two colours, so one colour appears $\geq 3$ times
same-colour lines (say red)	3	three dots all joined red to the sixth
lines among those three dots	3	if any is red, a red triangle appears
if none of the three is red	all blue	the three dots form a blue triangle

Either way a same-colour triangle appears. Six dots cannot escape, so the threshold is exactly six.

Worked example Beginner

Show by hand that any group of six people contains three mutual acquaintances or three mutual strangers.

Step 1. Pick one person, call her Ana. The other five people are each either an acquaintance or a stranger to Ana. That is five relationships, each one of two kinds.

Step 2. Split five into two kinds. Five things sorted into two boxes must overpack one box: at least three of Ana's five relationships are the same kind. Suppose at least three are acquaintances; call three of those acquaintances Beba, Cira, and Dina. (If instead three were strangers, the rest of the argument runs the same with the words swapped.)

Step 3. Look among Beba, Cira, Dina. Consider the three pairs Beba-Cira, Beba-Dina, Cira-Dina. If even one of these three pairs is a pair of acquaintances, then that pair together with Ana makes three mutual acquaintances, because Ana already knows both. We are done in that case.

Step 4. Handle the remaining case. If none of the three pairs is a pair of acquaintances, then Beba, Cira, and Dina are pairwise strangers. That is three mutual strangers, and we are done again.

What this tells us: there is no escape route. Every branch of the reasoning ends in three-of-a-kind. The only choices were "at least three same-kind" in Step 2 and "some pair matches or none does" in Step 4, and both choices lead to a same-kind triple. Six is enough to force the pattern, which is exactly the statement $R (3, 3) = 6$ .

Check your understanding Beginner

Formal definition Intermediate+

Fix a complete graph $K_{n}$ on $n$ vertices and a set of $r$ colours. An $r$ -colouring of the edges is a map $c : E (K_{n}) \to {1, \dots, r}$ . A subset $S \subseteq V (K_{n})$ is monochromatic if all edges inside $S$ receive the same colour; if $∣ S ∣ = k$ this is a monochromatic $K_{k}$ ^{[Diestel 2017 §9.1]}. The graph $K_{k}$ here is the complete graph on $k$ vertices, an object defined in the graph foundations 40.04.01.

Definition (Ramsey number). For integers $k \geq 1$ and $r \geq 1$ , the Ramsey number $R_{r} (k)$ is the least $n$ such that every $r$ -colouring of $E (K_{n})$ contains a monochromatic $K_{k}$ . For two colours one writes the off-diagonal number $R (s, t)$ : the least $n$ such that every red/blue colouring of $E (K_{n})$ contains a red $K_{s}$ or a blue $K_{t}$ . The diagonal number is $R (k, k) = R_{2} (k)$ , and $R (s, t) = R (t, s)$ by swapping colours. By convention $R (1, t) = 1$ and $R (2, t) = t$ , since a single red edge is a red $K_{2}$ and otherwise all edges are blue.

That $R_{r} (k)$ is finite — that the least such $n$ exists at all — is the content of Ramsey's theorem below; the definition presupposes existence, which the theorem supplies.

Definition (the hypergraph form). Write $[X]^{p}$ for the set of $p$ -element subsets of $X$ . A colouring of $p$ -subsets of $X$ with $r$ colours is a map $c : [X]^{p} \to {1, \dots, r}$ , and $Y \subseteq X$ is monochromatic if $c$ is constant on $[Y]^{p}$ . The edge version is the case $p = 2$ . The general Ramsey number $R_{r}^{(p)} (k)$ is the least $n$ with: every $r$ -colouring of $[{1, \dots, n}]^{p}$ has a monochromatic $k$ -subset.

Definition (partition regularity). A system of linear equations over $Z$ is partition regular if, for every finite colouring of the positive integers $N = C_{1} \cup \dots \cup C_{r}$ , some colour class $C_{i}$ contains a solution with all variables in $C_{i}$ . Schur's equation $x + y = z$ and the van der Waerden configuration "an arithmetic progression of length $k$ " are the model cases; Rado's theorem characterises which systems are partition regular.

Counterexamples to common slips

Monochromatic means same colour on every internal edge, not most. On $K_{4}$ a red triangle plus one blue edge is not a monochromatic $K_{4}$ ; the witness must be complete in a single colour. A $K_{4}$ with five red edges and one blue still has no red $K_{4}$ .
The threshold is sharp, so lower bounds need a colouring. Stating $R (3, 3) \leq 6$ is the easy half; proving $R (3, 3) > 5$ requires exhibiting a colouring of $K_{5}$ with no monochromatic triangle (the pentagon/pentagram). Upper bounds are forcing arguments; lower bounds are constructions.
More colours change the number. $R (3, 3) = 6$ is the two-colour value; the three-colour triangle number $R_{3} (3) = 17$ is different, and $R_{4} (3)$ is not even known exactly. Fixing $r$ matters.
Off-diagonal is not symmetric in the obvious way. $R (s, t) = R (t, s)$ holds, but $R (s, t)$ is governed by the larger of $s, t$ in a subtle way; for fixed $s$ , $R (s, t)$ grows polynomially in $t$ , not exponentially.

Key theorem with proof Intermediate+

Theorem (Ramsey's theorem and the Erdős-Szekeres bounds). For all integers $k, r \geq 1$ the Ramsey number $R_{r} (k)$ is finite. For two colours and $s, t \geq 2$ , $$ R(s, t) ;\le; R(s-1, t) + R(s, t-1), $$ and consequently $$ R(s, t) ;\le; \binom{s + t - 2}{s - 1}, \qquad R(k, k) ;\le; \binom{2k - 2}{k - 1} ;\le; 4^{k}. $$ (See ^{[Ramsey 1930]}; ^{[Erdős-Szekeres 1935]}; ^{[Diestel 2017 §9.1]}.)

Proof. The recursion. Suppose $R (s - 1, t)$ and $R (s, t - 1)$ are both finite, and set $n = R (s - 1, t) + R (s, t - 1)$ . Take any red/blue colouring of $K_{n}$ and fix a vertex $v$ . Its $n - 1$ incident edges split into the red-neighbour set $A$ and the blue-neighbour set $B$ , with $∣ A ∣ + ∣ B ∣ = n - 1 = R (s - 1, t) + R (s, t - 1) - 1$ . Were $∣ A ∣ \leq R (s - 1, t) - 1$ and $∣ B ∣ \leq R (s, t - 1) - 1$ both to hold, then $∣ A ∣ + ∣ B ∣ \leq R (s - 1, t) + R (s, t - 1) - 2 < n - 1$ , a contradiction; so $∣ A ∣ \geq R (s - 1, t)$ or $∣ B ∣ \geq R (s, t - 1)$ .

In the first case, the red-neighbourhood $A$ spans a complete graph on $\geq R (s - 1, t)$ vertices, hence contains a red $K_{s - 1}$ or a blue $K_{t}$ . A blue $K_{t}$ finishes the proof; a red $K_{s - 1}$ together with $v$ — joined in red to all of $A$ — yields a red $K_{s}$ . In the second case, symmetrically, $B$ contains a red $K_{s}$ or a blue $K_{t - 1}$ , and the blue $K_{t - 1}$ plus $v$ gives a blue $K_{t}$ . Either way the colouring has a red $K_{s}$ or a blue $K_{t}$ , so $R (s, t) \leq n$ .

Finiteness. The base cases $R (1, t) = R (s, 1) = 1$ and $R (2, t) = t$ , $R (s, 2) = s$ are finite, and the recursion produces every $R (s, t)$ from smaller ones, so all two-colour numbers are finite by induction on $s + t$ . For $r$ colours, group the last two colours into one to reduce $r$ to $r - 1$ : a monochromatic $K_{k}$ in the merged colour is a $K_{k}$ that is entirely colour $r - 1$ or entirely colour $r$ , which a further two-colouring of its edges resolves, giving $R_{r} (k) \leq R_{r - 1} (R_{2} (k))$ and finiteness by induction on $r$ .

The binomial bound. Induct on $s + t$ . The base $R (s, 1) = R (1, t) = 1 = (0 s - 1) = (0 t - 1)$ holds. For the step, Pascal's identity and the recursion give $$ R(s,t) \le R(s-1,t) + R(s,t-1) \le \binom{s+t-3}{s-2} + \binom{s+t-3}{s-1} = \binom{s+t-2}{s-1}. $$ Setting $s = t = k$ gives $R (k, k) \leq (k - 1 2 k - 2)$ , and $(k - 1 2 k - 2) \leq 2^{2 k - 2} = 4^{k - 1} \leq 4^{k}$ since a single binomial coefficient is at most the sum $2^{2 k - 2}$ of its row. $□$

Bridge. This theorem builds toward the whole of Ramsey theory and appears again in the probabilistic lower bound, the canonical theorem, and the density results below, because it is the prototype of every "large structure forces order" statement. The foundational reason the recursion works is the neighbourhood split: a single vertex partitions the rest by colour, and the pigeonhole forces one part large enough to recurse — this is exactly the inductive engine that the infinite Ramsey theorem runs to its limit and that van der Waerden's and Hales-Jewett's theorems re-enact in arithmetic and combinatorial-line settings. The upper bound $R (k, k) \leq 4^{k}$ is dual to the probabilistic lower bound $R (k, k) > 2^{k /2}$ proved in 40.07.01: putting these together pins the diagonal Ramsey number between bases $2$ and $4$ , the central insight that the exact growth of $R (k, k)$ is one of the hardest open problems in combinatorics, and the gap generalises into the off-diagonal and hypergraph regimes where even the order of magnitude is contested.

Exercises Intermediate+

Exercise 3 (medium, short-answer).

Prove that the recursion bound improves to a strict inequality, $R (s, t) \leq R (s - 1, t) + R (s, t - 1) - 1$ , whenever both $R (s - 1, t)$ and $R (s, t - 1)$ are even.

Hint

Set $n = R (s - 1, t) + R (s, t - 1) - 1$ , which is odd. In a red/blue colouring of $K_{n}$ , sum the red degrees; an odd number of vertices times something forces a vertex of even red degree.

Answer

Let $a = R (s - 1, t)$ , $b = R (s, t - 1)$ , both even, and put $n = a + b - 1$ , which is odd. In a red/blue colouring of $K_{n}$ , the red graph has an even degree sum (handshake lemma, 40.04.01), so with $n$ odd not all red degrees can be odd; pick a vertex $v$ of even red degree $d_{R} (v)$ . Its blue degree is $n - 1 - d_{R} (v) = a + b - 2 - d_{R} (v)$ . If $d_{R} (v) \leq a - 1$ then, $d_{R} (v)$ being even and $a - 1$ odd, in fact $d_{R} (v) \leq a - 2$ , so the blue degree is $\geq b$ ; if instead $d_{R} (v) \geq a$ , the red neighbourhood has $\geq a = R (s - 1, t)$ vertices. Either the red-neighbour set has $\geq R (s - 1, t)$ vertices or the blue-neighbour set has $\geq R (s, t - 1)$ vertices, and the standard recursion step then produces a red $K_{s}$ or blue $K_{t}$ . Hence $R (s, t) \leq n = a + b - 1$ . Rubric: full credit for the parity argument selecting an even-red-degree vertex and the resulting strict bound. (This is the trick giving $R (3, 4) \leq 9$ rather than $10$ .)

Exercise 5 (medium, short-answer).

State and prove the infinite Ramsey theorem for pairs: every red/blue colouring of the edges of the complete graph on $N$ contains an infinite monochromatic clique.

Hint

Build a sequence $v_{0}, v_{1}, \dots$ where at each stage you pass to an infinite set joined to the current vertex by a single colour. Then a colour repeats infinitely among the chosen "majority colours".

Answer

Set $S_{0} = N$ . Pick $v_{0} \in S_{0}$ . The edges from $v_{0}$ to the infinite set $S_{0} ∖ {v_{0}}$ are two-coloured, so one colour class is infinite; call it $c_{0}$ and let $S_{1}$ be that infinite set of $v_{0}$ -neighbours in colour $c_{0}$ . Pick $v_{1} \in S_{1}$ , split $S_{1} ∖ {v_{1}}$ by the colour of edges from $v_{1}$ , take an infinite class $S_{2}$ with colour $c_{1}$ , and continue. This yields an infinite sequence $v_{0}, v_{1}, \dots$ with colours $c_{0}, c_{1}, \dots \in {red, blue}$ such that the edge $v_{i} v_{j}$ ( $i < j$ ) has colour $c_{i}$ , since $v_{j} \in S_{i + 1}$ . Some colour, say red, occurs infinitely often among the $c_{i}$ ; the corresponding $v_{i}$ form an infinite set in which every edge is red — an infinite red clique. Rubric: full credit for the nested-infinite-set construction and the final pigeonhole on the majority colours.

Exercise 6 (hard, short-answer).

Deduce the finite Ramsey theorem for pairs from the infinite one by a compactness argument: if for every $n$ some red/blue colouring of $K_{n}$ avoided a monochromatic $K_{k}$ , derive an infinite colouring of $K_{N}$ avoiding an infinite monochromatic clique, contradicting Exercise 5.

Hint

The colourings of $K_{n}$ avoiding a monochromatic $K_{k}$ form an infinite, finitely-branching tree under restriction; apply König's lemma to extract an infinite branch.

Answer

Suppose, for contradiction, that for every $n$ there is a red/blue colouring $c_{n}$ of $K_{n}$ with no monochromatic $K_{k}$ . Build a tree whose level- $n$ nodes are the colourings of $K_{n}$ (on vertex set ${1, \dots, n}$ ) with no monochromatic $K_{k}$ , where a level- $(n + 1)$ node is a child of its restriction to ${1, \dots, n}$ . Each level is nonempty (some $c_{n}$ exists) and the tree is finitely branching (finitely many colourings at each level), so by König's lemma it has an infinite branch: a colouring $c$ of all of $K_{N}$ whose every finite restriction avoids a monochromatic $K_{k}$ . In particular $c$ has no monochromatic $K_{k}$ , hence no infinite monochromatic clique, contradicting the infinite Ramsey theorem of Exercise 5. Therefore some finite $n$ forces a monochromatic $K_{k}$ , which is the finite theorem; the least such $n$ is $R (k, k)$ . Rubric: full credit for the König-lemma tree, the infinite branch, and the contradiction with the infinite theorem.

Exercise 7 (hard, short-answer).

Prove Schur's theorem: for every $r$ there is a number $S (r)$ such that any $r$ -colouring of ${1, 2, \dots, S (r)}$ contains a monochromatic solution of $x + y = z$ (with $x, y, z$ the same colour, allowing $x = y$ ). Use Ramsey's theorem.

Hint

Given an $r$ -colouring of ${1, \dots, n}$ , colour the edge ${i, j}$ of $K_{n}$ (for $i < j$ ) by the colour of $j - i$ . Apply $R_{r} (3)$ and look at a monochromatic triangle $i < j < k$ .

Answer

Set $n = R_{r} (3)$ and let $χ : {1, \dots, n} \to {1, \dots, r}$ be any $r$ -colouring of the integers. Colour the edges of $K_{n}$ on vertex set ${1, \dots, n}$ by $c ({i, j}) = χ (∣ i - j ∣)$ . By definition of $R_{r} (3)$ there is a monochromatic triangle on vertices $i < j < k$ , so the three differences $j - i$ , $k - j$ , and $k - i$ all receive the same colour under $χ$ . Put $x = j - i$ , $y = k - j$ , $z = k - i$ ; then $x + y = z$ and $χ (x) = χ (y) = χ (z)$ , a monochromatic Schur triple. Thus $S (r) \leq R_{r} (3)$ suffices. Rubric: full credit for the difference-colouring reduction, the monochromatic triangle, and the identity $(j - i) + (k - j) = (k - i)$ . (Schur 1916 used this to show Fermat's congruence $x^{p} + y^{p} \equiv z^{p} (mod q)$ has nontrivial solutions for all large primes $q$ .)

Advanced results Master

Theorem 1 (the diagonal gap and small values). The diagonal numbers satisfy $2^{k /2} < R (k, k) \leq 4^{k}$ , the lower bound being Erdős's probabilistic estimate proved in 40.07.01 and the upper bound the Erdős-Szekeres count above. In $R (k, k)^{1/ k}$ this traps the growth base between $2$ and $4$ . The constant $4$ stood from 1935 until Campos, Griffiths, Morris, and Sahasrabudhe (2023) obtained $R (k, k) \leq (4 - ε)^{k}$ for an absolute $ε > 0$ ; no exponential improvement to the lower base $2$ is known. Exact values are known only for tiny cases: $R (3, 3) = 6$ , $R (4, 4) = 18$ , and $R (5, 5)$ is merely bracketed $43 \leq R (5, 5) \leq 46$ . Erdős dramatised the difficulty: if hostile aliens demanded the value of $R (5, 5)$ we should marshal every computer and mathematician to find it, but if they asked for $R (6, 6)$ we should attempt to destroy the aliens first.

Theorem 2 (the canonical Ramsey theorem of Erdős-Rado). When the number of colours is unbounded — a colouring $c : [N]^{p} \to N$ with no finiteness restriction — one cannot force a monochromatic infinite set. Erdős and Rado (1950) proved the exact replacement: for every $p$ there is a finite list of canonical colouring patterns on $[\cdot]^{p}$ such that every colouring of $[N]^{p}$ has an infinite subset on which $c$ agrees with one canonical pattern. For pairs ( $p = 2$ ) the four canonical patterns are: constant; "colour determined by the smaller element"; "colour determined by the larger element"; and "all distinct" (the rainbow pattern, $c$ injective on the subset). Ramsey's theorem is the special case where only the constant pattern can occur because the colour palette is finite.

Theorem 3 (van der Waerden and Hales-Jewett). Van der Waerden's theorem (1927): for all $k, r$ there is $W (k, r)$ such that every $r$ -colouring of ${1, \dots, W (k, r)}$ contains a monochromatic arithmetic progression of length $k$ . Its abstract source is the Hales-Jewett theorem (1963): for all $k, r$ there is a dimension $N = H J (k, r)$ such that every $r$ -colouring of the cube ${1, \dots, k}^{N}$ contains a monochromatic combinatorial line — a set of $k$ points obtained by fixing some coordinates and letting a nonempty set of "active" coordinates run together through $1, \dots, k$ . Hales-Jewett is the pinnacle from which van der Waerden (project a line to its arithmetic progression of coordinate-sums) and Gallai's multidimensional theorem follow by colour-preserving reductions; it is purely combinatorial, with no arithmetic input.

Theorem 4 (Rado's theorem and Schur). Schur's theorem (1916) — every finite colouring of $N$ has a monochromatic solution of $x + y = z$ — is the first partition-regularity result. Rado's theorem (1933) characterises all partition-regular linear systems: a system $A x = 0$ with integer matrix $A$ is partition regular iff $A$ satisfies the columns condition — the columns can be ordered and grouped into blocks $B_{1}, \dots, B_{m}$ so that each block's sum lies in the rational span of the earlier blocks' columns, with the first block summing to zero. Schur's equation $x + y - z = 0$ has column vector sum $1 + 1 - 1 = 1 \neq = 0$ but satisfies the columns condition with the single nonzero-but-spanning grouping; van der Waerden's length- $k$ progression is the partition regularity of the system $x_{i + 1} - x_{i} = d$ .

Theorem 5 (from partition to density: Szemerédi). Ramsey-type theorems guarantee a monochromatic pattern in some colour class; the deeper density versions guarantee the pattern in any sufficiently dense set, regardless of colouring. Szemerédi's theorem (1975): every subset of $N$ of positive upper density contains arbitrarily long arithmetic progressions, with van der Waerden as the immediate corollary (some colour class has positive density). The density Hales-Jewett theorem (Furstenberg-Katznelson 1991) plays the same apex role for combinatorial lines, and the Green-Tao theorem (2008) extends Szemerédi to the primes despite their vanishing density. The infinite-set Ramsey theory of $[N]^{p}$ and these density theorems are the two directions in which the finite combinatorial core of this unit deepens.

Synthesis. Putting these together, the foundational reason Ramsey theory coheres is a single mechanism seen at every scale: a large enough host structure, finitely coloured, contains a monochromatic copy of any fixed target, and the neighbourhood-split induction of the Key theorem is the prototype that the infinite, arithmetic, and combinatorial-line versions each re-enact. The diagonal gap $2 \leq R (k, k)^{1/ k} \leq 4$ is exactly the dual pairing of the probabilistic lower bound of 40.07.01 against the Erdős-Szekeres forcing count, so closing it is the open problem of beating either the random construction from below or the recursion from above — the central insight that quantitative Ramsey theory is genuinely hard where the qualitative theory is clean. The canonical theorem generalises Ramsey to unbounded palettes by replacing "monochromatic" with "one of finitely many canonical patterns", and this is exactly the move that keeps a finiteness conclusion alive when the colour count is infinite. Hales-Jewett is dual to van der Waerden: the abstract combinatorial line projects to the arithmetic progression, so the arithmetic theorem is a shadow of a purely set-theoretic one, and Rado's columns condition is the bridge that turns "which configurations are forced" into a decidable algebraic test. The density theorems of Szemerédi and Green-Tao are the bridge onward, trading the colouring hypothesis for a density hypothesis and thereby subsuming the partition results, the deepest current form of the slogan that complete disorder is impossible.

Full proof set Master

Proposition 1 (Erdős-Szekeres recursion and finiteness). For $s, t \geq 2$ , $R (s, t) \leq R (s - 1, t) + R (s, t - 1)$ , and every $R_{r} (k)$ is finite.

Proof. With $n = R (s - 1, t) + R (s, t - 1)$ and any red/blue colouring of $K_{n}$ , fix $v$ and partition the other $n - 1$ vertices into the red-neighbour set $A$ and blue-neighbour set $B$ . Since $∣ A ∣ + ∣ B ∣ = n - 1 = R (s - 1, t) + R (s, t - 1) - 1$ , not both $∣ A ∣ \leq R (s - 1, t) - 1$ and $∣ B ∣ \leq R (s, t - 1) - 1$ can hold, so $∣ A ∣ \geq R (s - 1, t)$ or $∣ B ∣ \geq R (s, t - 1)$ . In the former case $K_{A}$ contains a blue $K_{t}$ (done) or a red $K_{s - 1}$ , which with $v$ gives a red $K_{s}$ ; in the latter $K_{B}$ contains a red $K_{s}$ (done) or a blue $K_{t - 1}$ , which with $v$ gives a blue $K_{t}$ . Thus $R (s, t) \leq n$ . The base values $R (s, 1) = R (1, t) = 1$ are finite, so induction on $s + t$ makes all two-colour numbers finite. For $r \geq 3$ colours, merge colours $r - 1$ and $r$ into one to obtain an $(r - 1)$ -colouring; a monochromatic $K_{R_{2} (k)}$ in the merged colour is two-coloured internally and yields a monochromatic $K_{k}$ , giving $R_{r} (k) \leq R_{r - 1} (R_{2} (k))$ and finiteness by induction on $r$ . $□$

Proposition 2 (binomial and exponential upper bounds). $R (s, t) \leq (s - 1 s + t - 2)$ , and $R (k, k) \leq (k - 1 2 k - 2) \leq 4^{k}$ .

Proof. Induct on $s + t$ . For $s = 1$ or $t = 1$ , $R = 1 = (s - 1 s + t - 2)$ (one of the two lower indices is $0$ ). For the step, Proposition 1 and Pascal's rule give $$ R(s,t) \le R(s-1,t) + R(s,t-1) \le \binom{s+t-3}{s-2} + \binom{s+t-3}{s-1} = \binom{s+t-2}{s-1}. $$ At $s = t = k$ , $R (k, k) \leq (k - 1 2 k - 2)$ . The whole row of $(\cdot 2 k - 2)$ sums to $2^{2 k - 2}$ , so a single entry is at most $2^{2 k - 2} = 4^{k - 1} \leq 4^{k}$ . $□$

Proposition 3 (lower bound $R (3, 3) > 5$ and exact value). $R (3, 3) = 6$ .

Proof. Upper bound: Proposition 1 gives $R (3, 3) \leq R (2, 3) + R (3, 2) = 3 + 3 = 6$ . Lower bound: colour $K_{5}$ on vertices $Z /5$ by making ${i, j}$ red iff $i - j \equiv \pm 1 (mod 5)$ (the outer pentagon) and blue iff $i - j \equiv \pm 2 (mod 5)$ (the inner pentagram). The red graph is the 5-cycle $C_{5}$ and the blue graph is also a $5$ -cycle; neither contains a triangle, since $C_{5}$ is triangle-free. Hence this colouring of $K_{5}$ has no monochromatic triangle, so $R (3, 3) > 5$ . Together $R (3, 3) = 6$ . $□$

Proposition 4 (infinite Ramsey theorem for $p$ -sets). For every $p, r \geq 1$ and every colouring $c : [N]^{p} \to {1, \dots, r}$ there is an infinite $M \subseteq N$ with $c$ constant on $[M]^{p}$ .

Proof. Induct on $p$ . For $p = 1$ this is the pigeonhole principle: an $r$ -colouring of $N$ has an infinite monochromatic class. Assume the claim for $p - 1$ . Given $c$ on $[N]^{p}$ , build a sequence $a_{1}, a_{2}, \dots$ and infinite sets $N = N_{0} \supseteq N_{1} \supseteq \dots$ as follows. Having chosen $a_{i}$ and infinite $N_{i}$ , pick $a_{i + 1} = min (N_{i} ∖ {a_{1}, \dots, a_{i}})$ and define a colouring $c_{i}$ of $[N_{i} ∖ {a_{i + 1}}]^{p - 1}$ by $c_{i} (F) = c ({a_{i + 1}} \cup F)$ . By the induction hypothesis there is an infinite $N_{i + 1} \subseteq N_{i} ∖ {a_{i + 1}}$ on which $c_{i}$ is constant, with value $γ_{i} \in {1, \dots, r}$ . The colour $γ_{i}$ has the property that every $p$ -set ${a_{i + 1}} \cup F$ with $F \in [N_{i + 1}]^{p - 1}$ — in particular with $F \subseteq {a_{i + 2}, a_{i + 3}, \dots}$ — has colour $γ_{i}$ . Some value $γ$ occurs for infinitely many $i$ ; let $M = {a_{i} : γ_{i - 1} = γ}$ . For any $p$ -subset ${a_{i_{1}}, \dots, a_{i_{p}}}$ of $M$ with $i_{1} < \dots < i_{p}$ , its colour is $γ_{i_{1} - 1} = γ$ by construction, so $c$ is constant $γ$ on $[M]^{p}$ . $□$

Proposition 5 (Schur's theorem). For every $r$ there is $S (r)$ such that every $r$ -colouring of ${1, \dots, S (r)}$ has a monochromatic solution of $x + y = z$ ; indeed $S (r) \leq R_{r} (3)$ .

Proof. Put $n = R_{r} (3)$ and let $χ$ be an $r$ -colouring of ${1, \dots, n}$ . Colour edge ${i, j}$ of $K_{n}$ ( $i < j$ ) with $χ (j - i)$ . The number $R_{r} (3)$ forces a monochromatic triangle $i < j < k$ , whence $χ (j - i) = χ (k - j) = χ (k - i)$ . Set $x = j - i$ , $y = k - j$ , $z = k - i$ ; then $x + y = z$ and all three share a colour. So $S (r) \leq R_{r} (3)$ . $□$

Proposition 6 (van der Waerden from Hales-Jewett). The Hales-Jewett theorem implies van der Waerden's theorem.

Proof. Fix $k, r$ and let $N = H J (k, r)$ . Given an $r$ -colouring $χ$ of ${0, 1, \dots, k \cdot N}$ (translate so progressions start at $0$ ), colour the cube ${0, 1, \dots, k - 1}^{N}$ by $ϕ (w) = χ (w_{1} + \dots + w_{N})$ , an $r$ -colouring of $k$ symbols per coordinate. By Hales-Jewett (applied to the alphabet ${0, \dots, k - 1}$ ) there is a monochromatic combinatorial line: a set of points obtained by fixing coordinates outside an active set $I \neq = \emptyset$ and letting the active coordinates equal a common value $λ \in {0, \dots, k - 1}$ . As $λ$ runs $0, 1, \dots, k - 1$ , the coordinate-sum $w_{1} + \dots + w_{N} = (fixed part) + ∣ I ∣ \cdot λ$ runs through an arithmetic progression of length $k$ with common difference $∣ I ∣ \geq 1$ , all of whose terms receive a single colour under $χ$ . This is a monochromatic $k$ -term arithmetic progression, so $W (k, r) \leq k \cdot H J (k, r)$ is finite. $□$

Connections Master

The probabilistic method: first-moment and counting arguments 40.07.01. That unit owns the lower bound $R (k, k) > 2^{k /2}$ , proved by colouring $K_{n}$ at random and computing that the expected number of monochromatic $K_{k}$ is below one when $(k n) 2^{1 - (2 k)} < 1$ . This unit supplies the matching upper bound $R (k, k) \leq 4^{k}$ by the Erdős-Szekeres forcing recursion. Together they trap $R (k, k)^{1/ k}$ between $2$ and $4$ ; the two arguments are the same clique-count read in opposite directions — existence-by-averaging versus existence-by-pigeonhole — and the persistence of the gap is the headline open problem both units point at.
Graphs, basic invariants, and the foundational lemmas 40.04.01. Ramsey's theorem is a statement about complete graphs, monochromatic cliques, and vertex neighbourhoods, all defined there; the neighbourhood split that drives the recursion is exactly the degree/adjacency bookkeeping of that unit, and the parity refinement of Exercise 3 invokes the handshake lemma directly. The triangle-free $C_{5}$ certifying $R (3, 3) > 5$ is a cycle in the sense fixed there.
Extremal graph theory: Turán's theorem and the Erdős-Stone-Simonovits theorem 40.05.01 and the Szemerédi regularity lemma and triangle removal 40.05.03. The co-produced extremal unit 40.05.01 and the regularity unit 40.05.03 are the density side of the same chapter: where Ramsey forces a monochromatic clique in some colour class, Turán-type results force a clique once the edge density crosses a threshold, and the regularity lemma of 40.05.03 is the engine behind the density Ramsey theorems (Szemerédi, removal lemma) that this unit points to as its deepest generalisation. Ramsey colourings and extremal edge bounds are the two halves of how local order is forced in dense graphs.

Historical & philosophical context Master

The theorem is due to Frank Plumpton Ramsey, who proved both the finite and infinite partition theorems in his 1930 paper On a problem of formal logic (Proceedings of the London Mathematical Society, 2nd series, 30) ^{[Ramsey 1930]}. Ramsey's goal was not combinatorics: he wanted a decision procedure for a fragment of first-order logic (the $\exists\forall$ Bernays-Schönfinkel class), and the partition theorem was a lemma. He died in 1930 at twenty-six, and the combinatorial theorem outgrew the logical application that motivated it. The quantitative theory began with Paul Erdős and George Szekeres, whose 1935 A combinatorial problem in geometry (Compositio Mathematica 2) ^{[Erdős-Szekeres 1935]} rediscovered the finite theorem, proved the recursion and the binomial bound, and applied it to show that sufficiently many points in general position contain a convex polygon of any prescribed size — the "happy ending problem", so named because it led to the marriage of Szekeres and Esther Klein.

The partition-regularity strand is older in part: Issai Schur proved the monochromatic $x + y = z$ result in 1916 while studying Fermat's congruence, and Bartel van der Waerden proved the monochromatic-arithmetic-progression theorem in 1927. Richard Rado, Schur's student, characterised all partition-regular linear systems in his 1933 dissertation. The abstract apex, the combinatorial-line theorem, is due to Alfred Hales and Robert Jewett in 1963 (Transactions of the American Mathematical Society 106) ^{[Hales-Jewett 1963]}. Richard Rado and Erdős established the canonical Ramsey theorem in 1950, settling the unbounded-colour case. The density turn came with Endre Szemerédi's 1975 proof that positive-density sets contain long progressions, for which the regularity lemma was invented; the textbook organisation followed in Diestel's Graph Theory ^{[Diestel 2017]} and the monograph of Graham, Rothschild, and Spencer ^{[Graham-Rothschild-Spencer 1990]}.

Bibliography Master

@article{Ramsey1930,
  author  = {Ramsey, Frank P.},
  title   = {On a problem of formal logic},
  journal = {Proceedings of the London Mathematical Society},
  series  = {2},
  volume  = {30},
  year    = {1930},
  pages   = {264--286}
}

@article{ErdosSzekeres1935,
  author  = {Erd\H{o}s, Paul and Szekeres, George},
  title   = {A combinatorial problem in geometry},
  journal = {Compositio Mathematica},
  volume  = {2},
  year    = {1935},
  pages   = {463--470}
}

@article{Schur1916,
  author  = {Schur, Issai},
  title   = {\"Uber die Kongruenz $x^m + y^m \equiv z^m \pmod p$},
  journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung},
  volume  = {25},
  year    = {1916},
  pages   = {114--117}
}

@article{vanderWaerden1927,
  author  = {van der Waerden, Bartel L.},
  title   = {Beweis einer Baudetschen Vermutung},
  journal = {Nieuw Archief voor Wiskunde},
  volume  = {15},
  year    = {1927},
  pages   = {212--216}
}

@phdthesis{Rado1933,
  author  = {Rado, Richard},
  title   = {Studien zur Kombinatorik},
  school  = {University of Berlin},
  year    = {1933},
  note    = {published in Mathematische Zeitschrift 36 (1933) 424--470}
}

@article{HalesJewett1963,
  author  = {Hales, Alfred W. and Jewett, Robert I.},
  title   = {Regularity and positional games},
  journal = {Transactions of the American Mathematical Society},
  volume  = {106},
  year    = {1963},
  pages   = {222--229}
}

@article{ErdosRado1950,
  author  = {Erd\H{o}s, Paul and Rado, Richard},
  title   = {A combinatorial theorem},
  journal = {Journal of the London Mathematical Society},
  volume  = {25},
  year    = {1950},
  pages   = {249--255}
}

@article{Szemeredi1975,
  author  = {Szemer\'edi, Endre},
  title   = {On sets of integers containing no $k$ elements in arithmetic progression},
  journal = {Acta Arithmetica},
  volume  = {27},
  year    = {1975},
  pages   = {199--245}
}

@article{Campos2023,
  author  = {Campos, Marcelo and Griffiths, Simon and Morris, Robert and Sahasrabudhe, Julian},
  title   = {An exponential improvement for diagonal Ramsey},
  journal = {arXiv preprint arXiv:2303.09521},
  year    = {2023}
}

@book{GrahamRothschildSpencer1990,
  author    = {Graham, Ronald L. and Rothschild, Bruce L. and Spencer, Joel H.},
  title     = {Ramsey Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {1990}
}

Prerequisites

40.04.01

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §9.1 (Ramsey's theorem) read for the party / two-colour pictures; the folklore 'party of six' puzzle that every gathering of six has three mutual acquaintances or three mutual strangers; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §8.3 for the small two-colouring drawings
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §9.1 (Ramsey's theorem, the recursion $R(s,t)\le R(s-1,t)+R(s,t-1)$, the $\binom{s+t-2}{s-1}$ and $4^k$ bounds, $R(3,3)=6$, the infinite Ramsey theorem); Graham-Rothschild-Spencer 1990 *Ramsey Theory* (2nd ed., Wiley) Ch. 1-4; Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) §12.5
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §9.1-§9.4 (Ramsey's theorem, induced Ramsey, the canonical Ramsey theorem of Erdős-Rado); Graham-Rothschild-Spencer 1990 *Ramsey Theory* (2nd ed., Wiley) Ch. 1-7 (van der Waerden, Hales-Jewett, Rado's theorem, the canonical theorem); the original sources Ramsey 1930 (*Proc. London Math. Soc.*), Erdős-Szekeres 1935 (*Compositio Math.*), Erdős 1947 (*Bull. AMS*), Schur 1916, van der Waerden 1927, Hales-Jewett 1963, Szemerédi 1975

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, Ch. 9 (§9.1 Ramsey's original theorem and the recursion R(s,t) <= R(s-1,t)+R(s,t-1) with the binomial upper bound; §9.2 Ramsey numbers and small values; §9.3 induced Ramsey theorems; §9.4 Ramsey theory for graphs and the canonical Ramsey theorem)
Ramsey, F. P. — On a problem of formal logic · Proceedings of the London Mathematical Society (2) 30 (1930) 264-286; the finite and infinite partition theorems now called Ramsey's theorem, proved as a lemma toward a decision problem for a fragment of first-order logic
Erdős, P. & Szekeres, G. — A combinatorial problem in geometry · Compositio Mathematica 2 (1935) 463-470; the recursion R(s,t) <= R(s-1,t)+R(s,t-1), the bound R(s,t) <= binom(s+t-2,s-1), and the happy-ending convex-polygon application
Graham, Rothschild, Spencer — Ramsey Theory · Wiley, 2nd edition (1990). Ch. 1-7: the finite and infinite Ramsey theorems, Schur's theorem, van der Waerden's theorem, the Hales-Jewett theorem, Rado's theorem on partition-regular systems, and the Erdős-Rado canonical Ramsey theorem
Hales, A. W. & Jewett, R. I. — Regularity and positional games · Transactions of the American Mathematical Society 106 (1963) 222-229; the Hales-Jewett theorem on monochromatic combinatorial lines, the abstract core from which van der Waerden's and Gallai's theorems follow

Estimated time

beginner: 17m
intermediate: 47m
master: 86m