Capstone: Ramsey theory and the probabilistic method

The capstone brings together the threads of the course: counting, existence, extremal bounds and algorithms. Its subject is a principle that complete disorder is impossible. However the edges of a large enough complete graph are coloured, some large piece is monochromatic; however the integers are split into finitely many classes, one class contains long arithmetic progressions. Proving such statements uses pigeonhole arguments like those of lesson 1. Showing that the bounds are not far from the truth uses the probabilistic method, which proves that objects exist by showing that a random one works with positive probability. Both ideas are associated above all with Paul Erdős, who wrote around 1,500 papers with more than 500 collaborators.

The party problem

Among any six people, there are three who all know each other or three who are mutual strangers. In graph language: colour each edge of \(K_6\) red or blue; then there is a monochromatic triangle.

Proof. Fix a vertex \(v\). It has five edges, so by pigeonhole at least three have the same colour, say red, to vertices \(x\), \(y\), \(z\). If any edge among \(x\), \(y\), \(z\) is red, it forms a red triangle with \(v\). Otherwise \(xy\), \(yz\) and \(xz\) are all blue, a blue triangle.

Six is the smallest number that works. Colour the edges of a pentagon red and its diagonals, which form a pentagram, blue. Each colour class is a 5-cycle, which has no triangle. So the Ramsey number \(R(3, 3)\), the least \(n\) such that every red–blue colouring of \(K_n\) has a red \(K_3\) or a blue \(K_3\), equals 6.

Ramsey's theorem

Define \(R(s, t)\) as the least \(n\) such that every red–blue colouring of the edges of \(K_n\) contains a red \(K_s\) or a blue \(K_t\). Equivalently, every graph on \(n\) vertices contains a clique of size \(s\) or an independent set of size \(t\). It is not obvious that such an \(n\) exists at all.

Theorem (Ramsey, 1930; Erdős and Szekeres, 1935). \(R(s, t)\) is finite for all \(s, t \ge 1\), and \[R(s, t) \le R(s - 1, t) + R(s, t - 1), \qquad R(s, t) \le \binom{s + t - 2}{s - 1}.\]

Proof. Clearly \(R(s, 1) = R(1, t) = 1\). Let \(n = R(s - 1, t) + R(s, t - 1)\), colour \(K_n\), and fix a vertex \(v\). Its \(n - 1\) other vertices split into \(A\), joined to \(v\) by red edges, and \(B\), joined by blue edges. Since \(|A| + |B| = n - 1\), either \(|A| \ge R(s - 1, t)\) or \(|B| \ge R(s, t - 1)\). In the first case \(A\) contains a blue \(K_t\), and we are done, or a red \(K_{s-1}\), which together with \(v\) forms a red \(K_s\). The second case is symmetric. The binomial bound follows by induction, since \(\binom{s+t-3}{s-2} + \binom{s+t-3}{s-1} = \binom{s+t-2}{s-1}\) by Pascal's rule.

Frank Ramsey proved a more general statement in 1930 as a lemma in a paper on the decision problem in logic; he died that year aged 26. The theorem became widely known through the 1935 paper of Erdős and George Szekeres, which proved the binomial bound and the result on convex polygons below. In particular \(R(k, k) \le \binom{2k - 2}{k - 1} < 4^k\).

Known values. Very few Ramsey numbers are known exactly: \(R(3, 3) = 6\), \(R(3, 4) = 9\), \(R(3, 5) = 14\), \(R(4, 4) = 18\) (Greenwood and Gleason, 1955) and \(R(4, 5) = 25\) (McKay and Radziszowski, 1995, using extensive computation). For \(R(5, 5)\) it is known only that \(43 \le R(5, 5) \le 46\), the upper bound proved by Angeltveit and McKay in 2024. Erdős liked to say that if aliens demanded the value of \(R(5, 5)\) on pain of destroying the Earth, we should marshal all our computers and mathematicians to find it; but if they asked for \(R(6, 6)\), we should try to destroy the aliens.

Several colours. The same argument shows that for any number of colours \(r\), every \(r\)-colouring of a large enough complete graph has a monochromatic triangle; \(R(3, 3, 3) = 17\). Issai Schur deduced in 1916 a statement about numbers: if \(\{1, \ldots, N\}\) is split into \(r\) classes and \(N\) is large enough, some class contains \(x\), \(y\) and \(x + y\). Proof: colour the edge \(ij\) of \(K_{N+1}\) on vertices \(0, \ldots, N\) by the class of \(|i - j|\). A monochromatic triangle \(i < j < k\) gives \(x = j - i\), \(y = k - j\) and \(x + y = k - i\) in the same class. Schur used this to show that Fermat's equation \(x^m + y^m = z^m\) has nontrivial solutions modulo every sufficiently large prime.

Order in other settings

Convex polygons. Erdős and Szekeres proved that for every \(k\) there is \(N(k)\) such that any \(N(k)\) points in the plane, no three on a line, contain \(k\) points forming a convex polygon. For \(k = 4\), five points suffice, a fact noticed by Esther Klein; her collaboration on the problem led to her marriage to Szekeres, and Erdős called it the happy ending problem. Erdős and Szekeres conjectured \(N(k) = 2^{k-2} + 1\); \(N(6) = 17\) was confirmed by computer in 2006, and in 2017 Andrew Suk proved \(N(k) \le 2^{k + o(k)}\), nearly settling the conjecture.

Arithmetic progressions. Bartel van der Waerden proved in 1927 that if the positive integers are split into finitely many classes, one class contains arithmetic progressions of every length. Endre Szemerédi proved in 1975 that any set of integers with positive upper density contains such progressions, and Ben Green and Terence Tao proved in 2004 that the primes do. Results of this kind, that large or dense structures must contain ordered substructures, form Ramsey theory.

The probabilistic method

How large must \(R(k, k)\) be? A lower bound requires a colouring of \(K_n\) with no monochromatic \(K_k\), and explicit constructions are surprisingly hard to find. Erdős found a way to avoid constructing anything.

Theorem (Erdős, 1947). If \(\binom{n}{k}2^{1 - \binom{k}{2}} < 1\), then \(R(k, k) > n\). In particular \(R(k, k) > 2^{k/2}\) for all \(k \ge 3\).

Proof. Colour each edge of \(K_n\) red or blue independently with probability \(\frac12\). For a fixed set \(S\) of \(k\) vertices, the probability that all \(\binom{k}{2}\) edges inside \(S\) get the same colour is \(2 \cdot 2^{-\binom{k}{2}}\). By the union bound of lesson 3, the probability that some \(k\)-set is monochromatic is at most \(\binom{n}{k}2^{1 - \binom{k}{2}} < 1\). So with positive probability no \(k\)-set is monochromatic, and therefore some colouring has none. For \(n = \lfloor 2^{k/2} \rfloor\), \(\binom{n}{k} < \frac{n^k}{k!} \le \frac{2^{k^2/2}}{k!}\), and \(2^{1 - k(k-1)/2} \cdot 2^{k^2/2}/k! = 2^{1 + k/2}/k! < 1\) for \(k \ge 3\).

So \(\sqrt2^{\,k} < R(k, k) < 4^k\). Remarkably, no explicit construction of a colouring achieving an exponential lower bound of this strength is known; the best constructions are far weaker. The upper bound \(4^k\) stood, up to lower-order factors, for 88 years, until Marcelo Campos, Simon Griffiths, Robert Morris and Julian Sahasrabudhe proved in 2023 that \(R(k, k) \le (4 - \varepsilon)^k\) for a small fixed \(\varepsilon > 0\), about \(3.993^k\), a breakthrough later improved by others. Whether the true growth rate is closer to \(\sqrt2\) or to 4 remains one of the main open problems of combinatorics.

Linearity of expectation. Often an existence argument needs only an average. Every graph with \(m\) edges has a bipartite subgraph with at least \(m/2\) edges. Proof: put each vertex on the left or right at random. Each edge crosses with probability \(\frac12\), so the expected number of crossing edges is \(m/2\), and some assignment does at least as well as the average. Similarly, a random permutation has on average one fixed point, as in lesson 3, and a random tournament on \(n\) players has on average \(n!/2^{n-1}\) Hamilton paths, which Tibor Szele used in 1943 in one of the first probabilistic proofs in combinatorics, showing that some tournament has at least that many.

Alteration and beyond. A refinement deletes the few bad parts of a random object: picking a random colouring and then deleting one vertex from each monochromatic \(K_k\) improves Erdős's bound slightly. More powerful tools include the second moment method, concentration inequalities and the Lovász local lemma of 1975, which shows that when bad events are each unlikely and mostly independent, with positive probability none occurs. Erdős used probabilistic arguments in 1959 to prove the existence of graphs with arbitrarily large girth and chromatic number, a result mentioned in lesson 9 that no one could prove constructively for years. Random graphs, introduced by Erdős and Alfréd Rényi in 1959 and 1960, became a subject in their own right, with sharp thresholds for properties such as connectivity and the appearance of a giant component.

Looking back

The course has developed a toolkit for finite structures. For counting: bijections, recurrences, inclusion and exclusion, and generating functions, ordinary for unlabelled objects and exponential for labelled ones, with asymptotics from singularities. For structure: Euler's formula and its consequences for planar graphs, colouring bounds and chromatic polynomials, augmenting paths and the duality theorems of König, Hall, Menger and Ford–Fulkerson, which say that a maximum of one kind equals a minimum of another. For existence: pigeonhole, invariants, and the probabilistic method. Many of these results come with efficient algorithms, while others, such as Hamilton cycles, 3-colourability and exact Ramsey numbers, are computationally hard, and recognizing which kind of problem one faces is itself part of the craft. Natural next steps are algorithms and complexity in CMPUT-204, probability in STAT courses, and algebraic and topological combinatorics in graduate study.

from itertools import combinations, product
from math import comb, factorial
import random

def has_mono_triangle(n, paint):
    return any(paint[(a, b)] == paint[(a, c)] == paint[(b, c)] for a, b, c in combinations(range(n), 3))

edges6 = list(combinations(range(6), 2))
bad = 0
for bits in product((0, 1), repeat=len(edges6)):
    if not has_mono_triangle(6, dict(zip(edges6, bits))):
        bad += 1
print("2-assignments of K6 edges:", 2 ** 15, " without a one-class triangle:", bad)

edges5 = list(combinations(range(5), 2))
pentagon = {(a, b): int((b - a) % 5 in (1, 4)) for a, b in edges5}
print("K5 pentagon/pentagram split has a one-class triangle:", has_mono_triangle(5, pentagon))
good5 = sum(not has_mono_triangle(5, dict(zip(edges5, bits))) for bits in product((0, 1), repeat=10))
print("number of K5 splits with no one-class triangle:", good5)

residues = {(x * x) % 17 for x in range(1, 17)}
paley = {(a, b): int((b - a) % 17 in residues) for a, b in combinations(range(17), 2)}
def mono_clique(n, paint, k):
    return any(len({paint[e] for e in combinations(S, 2)}) == 1 for S in combinations(range(n), k))
print("Paley graph on 17 vertices: one-class K4 exists?", mono_clique(17, paley, 4), " -> R(4,4) > 17")

def erdos_n(k):
    n = k
    while comb(n + 1, k) * 2 ** (1 - comb(k, 2)) < 1:
        n += 1
    return n
for k in [4, 5, 6, 10, 20]:
    print(f"k={k:2d}: Erdos guarantees R(k,k) > {erdos_n(k):6d};  2^(k/2) = {2 ** (k / 2):8.1f};  upper bound C(2k-2,k-1) = {comb(2 * k - 2, k - 1)}")

random.seed(1947)
k, n = 4, 6
trials = 2000
avoid = sum(not mono_clique(n, {e: random.randint(0, 1) for e in combinations(range(n), 2)}, k) for _ in range(trials))
expected_mono = comb(n, k) * 2 ** (1 - comb(k, 2))
print(f"random splits of K{n}: expected number of one-class K4 = {expected_mono:.2f}; fraction with none = {avoid / trials:.3f}")

petersen = [(i, (i + 1) % 5) for i in range(5)] + [(5 + i, 5 + (i + 2) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
best = max(sum(side[a] != side[b] for a, b in petersen) for side in product((0, 1), repeat=10))
avg = sum(sum(side[a] != side[b] for a, b in petersen) for side in product((0, 1), repeat=10)) / 2 ** 10
print(f"Petersen: average crossing edges over all 1024 sides = {avg}, best = {best}, m/2 = {len(petersen) / 2}")

def sum_free_split(N, r):
    for labels in product(range(r), repeat=N):
        ok = True
        for x in range(1, N + 1):
            for y in range(x, N + 1 - x):
                if labels[x - 1] == labels[y - 1] == labels[x + y - 1]:
                    ok = False; break
            if not ok:
                break
        if ok:
            return labels
    return None
for N in [4, 5]:
    print(f"split 1..{N} into 2 classes with no x, y, x+y in one class:", sum_free_split(N, 2))

n = 7
print(f"tournaments on {n} players: average number of Hamilton paths = n!/2^(n-1) =", factorial(n) / 2 ** (n - 1))

2-assignments of K6 edges: 32768  without a one-class triangle: 0
K5 pentagon/pentagram split has a one-class triangle: False
number of K5 splits with no one-class triangle: 12
Paley graph on 17 vertices: one-class K4 exists? False  -> R(4,4) > 17
k= 4: Erdos guarantees R(k,k) >      6;  2^(k/2) =      4.0;  upper bound C(2k-2,k-1) = 20
k= 5: Erdos guarantees R(k,k) >     11;  2^(k/2) =      5.7;  upper bound C(2k-2,k-1) = 70
k= 6: Erdos guarantees R(k,k) >     17;  2^(k/2) =      8.0;  upper bound C(2k-2,k-1) = 252
k=10: Erdos guarantees R(k,k) >    100;  2^(k/2) =     32.0;  upper bound C(2k-2,k-1) = 48620
k=20: Erdos guarantees R(k,k) >   5817;  2^(k/2) =   1024.0;  upper bound C(2k-2,k-1) = 35345263800
random splits of K6: expected number of one-class K4 = 0.47; fraction with none = 0.689
Petersen: average crossing edges over all 1024 sides = 7.5, best = 12, m/2 = 7.5
split 1..4 into 2 classes with no x, y, x+y in one class: (0, 1, 1, 0)
split 1..5 into 2 classes with no x, y, x+y in one class: None
tournaments on 7 players: average number of Hamilton paths = n!/2^(n-1) = 78.75

All 32,768 two-class splits of the edges of \(K_6\) contain a one-class triangle, while \(K_5\) has 12 splits without one, the pentagon and pentagram splits under relabelling. The Paley graph on 17 vertices, joining residues whose difference is a square modulo 17, has no one-class \(K_4\), which proves \(R(4, 4) \ge 18\); with the upper bound this gives the exact value. Erdős's bound grows like \(2^{k/2}\) while the Erdős–Szekeres upper bound grows like \(4^k\). In random splits of \(K_6\), the expected number of one-class \(K_4\) is about 0.47, below 1, and indeed most random splits contain none. A random side assignment cuts on average half the edges of the Petersen graph, and the best cuts 12. Finally, \(\{1, 2, 3, 4\}\) splits as \(\{1, 4\}\) and \(\{2, 3\}\) with no class containing \(x\), \(y\) and \(x + y\), but \(\{1, \ldots, 5\}\) cannot.