Chapter 14 · Special Topics
Ramsey Theory on Graphs
R(3,3)=6 and R(4,4)=18 with complete elementary proofs, the recursion behind every bound, and the counting argument that explains why the numbers explode.
#Ramsey numbers
R(s,t) is the least n such that every red/blue colouring of the edges of Kn contains a red Ks or a blue Kt. Equivalently: every graph on n ≥ R(s,t) vertices has a clique of size s or an independent set of size t (red = "edge"). Equality has two halves — every colouring of Kn forces the monochromatic clique, and some colouring of Kn-1 avoids both.
#The one case you can do by hand
Every 2-colouring of K6 has a monochromatic triangle, and there is a colouring of K5 with none.
Upper bound. Fix a vertex v of K6; its 5 incident edges have 3 of one colour by the pigeonhole principle, say va, vb, vc red. If an edge of the triangle abc is red, it completes a red triangle with v; otherwise a,b,c span a blue triangle. Lower bound. Colour K5 with the red edges forming a 5-cycle: both colour classes are triangle-free, so no monochromatic triangle exists. ∎
#The recursion behind every upper bound
Proof. Colour Kn with n = R(s-1,t) + R(s,t-1), and take a vertex v. Split its neighbours into the red set A and the blue set B; then |A| + |B| = n - 1, so either |A| ≥ R(s-1,t) or |B| ≥ R(s,t-1). In the first case, A contains a red Ks-1 (which together with v is a red Ks) or a blue Kt; the second case is symmetric. ∎
Telescoping from R(2,t)=t gives R(s,t) ≤ C(s+t-2, s-1), and hence R(k,k) ≤ 4k+o(k). One sharpening is worth knowing: if R(s-1,t) and R(s,t-1) are both even, the inequality is strict, R(s,t) ≤ R(s-1,t) + R(s,t-1) - 1 (otherwise a colouring of Kn-1 would force each vertex to have exactly R(s-1,t)-1 red neighbours, and the parity of the red degrees contradicts ∑ odd = even).
#Small exact values
R(3,3)=6, R(3,4)=9, R(3,5)=14, R(4,4)=18, R(3,6)=18, R(3,7)=23, R(3,8)=28, R(3,9)=36. R(5,5) is unknown; the best published range is 43 ≤ R(5,5) ≤ 48, and limk R(k,k)1/k is known only to lie in [√2, 4].
#Two hand-computed values: R(3,4) and R(4,4)
Upper bound: R(3,4) ≤ R(2,4) + R(3,3) = 4 + 6 = 10, and the parity strengthening (both terms even) gives R(3,4) ≤ 9. Lower bound: on 8 vertices take the circulant graph on ℤ8 joining i to i ± 1 and i+4 (the Möbius–Kantor cubic graph). It has 8 vertices, is triangle-free, and its independence number is 3 — so it has no red triangle and no independent set of size 4, i.e. a colouring of K8 with no red K3 and no blue K4. Hence R(3,4) > 8. ∎
Upper bound: R(4,4) ≤ R(3,4) + R(4,3) = 9 + 9 = 18 (the parity trick does not apply: 9 is odd). Lower bound: on 17 vertices, colour ij red iff i - j (mod 17) ∈ {±3, ±5, ±6, ±7}. Every vertex has red degree 8; checking all C(17, 4) = 2380 four-sets shows that no four vertices are pairwise red-adjacent and none are pairwise blue-adjacent. So R(4,4) ≥ 18, and with the upper bound, equality. (The check is 10 lines of code — worth running yourself once, as a reminder that "Ramsey lower bounds" are finite verifications, not mysticism.)
#The probabilistic lower bound
If C(n, k) 21-C(k, 2) < 1 then R(k,k) > n. In particular R(k,k) ≥ (21/2 - o(1))k.
Colour each of the C(n, 2) edges red/blue independently with probability ½. For a fixed k-set S, "S is monochromatic" has probability 2 · 2-C(k, 2), so by the union bound
With positive probability no monochromatic Kk exists, which proves such a colouring exists. Substituting C(n, k) ≤ (en/k)k and n = ⌊ 2k/2⌋, the exponent is klog2(en/k) + 1 - C(k, 2), negative for large k because k2/4 dominates k log k. ∎
#Reading the bounds correctly
Reading the bounds correctly
- the argument is non-constructive: it shows existence by a probability estimate; derandomising it (conditional expectations) gives a polynomial-time algorithm that finds such a colouring for that n, which is still not an explicit closed-form family,
- explicit constructions are far weaker — Paley-type graphs give R(k,k) ≥ kclog k, and closing the gap with 2k/2 is a central open problem,
- on the upper side, R(k,k) ≤ (4 - o(1))k (Sah, 2023) is the first asymptotic improvement over the classical 4k in decades, while the lower bound has stayed at (√2)k since Bohman–Keevash,
- the same computation with unequal sizes — C(n, s) 2-C(s, 2) + C(n, t) 2-C(t, 2) < 1 ⇒ R(s,t) > n — is how you prove "there exists a graph with no K4 and with independence number at most 4 on n vertices", which is what many "show the bound is tight" problems actually ask.
#How the arguments appear in contests
How these arguments appear in contests
- "6 people, 3 mutual friends or 3 mutual strangers" — the R(3,3)=6 pigeonhole paragraph; the only idea is which vertex to fix (usually the one of largest degree),
- three colours: R(3,3,3) = 17. Upper bound: in any 3-colouring of K17 some vertex has at least ⌈ 16/3 ⌉ = 6 incident edges of one colour, and R(3,3)=6 inside that neighbourhood gives the monochromatic triangle. Lower bound: a 3-colouring of K16 with no monochromatic triangle (two copies of the K5 construction glued appropriately) — the arithmetic ⌈ 16/3 ⌉ = 6 versus the mistaken ⌈ 16/3 ⌉ = 5 is the standard slip,
- sequence form: Erdős–Szekeres below, which is the same proof pattern (labels, distinctness, count),
- algorithmic extraction: the upper bound implies every graph on n vertices has a clique or independent set of size ≥ log2 n, and the proof is recursive — at a vertex v of degree ≥ n/2 recurse into N(v), else into the non-neighbours — giving a linear-time algorithm for a log n-sized homogeneous set,
- why "large homogeneous set" is a lower-bound tool: branching programs, range-query structures, and Ramsey-type arguments in geometry all use "either structure of size log n or nothing", so a log from Ramsey shows up in an nΩ(log n) bound.
#Erdős–Szekeres
Any sequence of ab + 1 distinct real numbers contains an increasing subsequence of length a+1 or a decreasing subsequence of length b+1. Proof. Label position i with (ℓi, di) = the lengths of the longest increasing and longest decreasing subsequence ending at i. If i < j and xi < xj then ℓj ≥ ℓi + 1; if i < j and xi > xj then dj ≥ di + 1. So no two positions share a label. But only ab labels lie in [a] × [b], so with ab + 1 positions some label escapes the box, giving the claim. The case a = b = k ("k2 + 1 numbers force a monotone subsequence of length k+1") is tight: take k decreasing blocks of size k, arranged in increasing order. ∎
#Four precision points
- A Ramsey value claim needs both directions; a solution that only proves "every colouring of K6 works" has proved R(3,3) ≤ 6.
- In the recursion, the pigeonhole split is on the neighbourhood of one vertex — the sets are |A| + |B| = n - 1, so the threshold is ⌈ (n-1)/2 ⌉, not n/2.
- The probabilistic bound gives existence for some n ≈ 2k/2; it never says "for all n" or "the graph is random-like" — a common overclaim in write-ups.
- If a problem asks for an explicit example, use the algebraic route (Paley graph on q ≡ 1 ±od 4 vertices: self-complementary, and every clique and independent set has size at most √q by the character-sum bound) — that is 4 lines and provable; do not try to "construct" from the probabilistic method.
- the true order of R(3,t): telescoping the recursion gives R(3,t) ≤ C(t, 2) + 1, and the probabilistic method gives the matching-order lower bound up to a logarithm, R(3,t) ≥ c t2 / log t (Ajtai–Komlós–Szemerédi and Kim). So the quadratic bound is off by exactly a log — worth knowing before claiming an "optimal" construction in an essay answer,
- monochromatic triangles are unavoidable in quantity: any 2-colouring of Kn has at least (tfrac14 - o(1))C(n, 3) monochromatic triangles (Goodman), and the random colouring attains it. Proof by double counting: count the "non-mono"cheromatic wedges C(n, 2)-wise, i.e. for each vertex count pairs of incident edges of different colours and sum — Double Counting and Averaging's exact technique. It is the one Ramsey-adjacent inequality that is both easy and asked in finals.