Skip to main content
Mind School·Wonder·Honor-system

Ramsey Numbers

How large must a structure be before order is unavoidable? No one knows for most cases.

Play It

▶

Coming Soon

Characterization

Ramsey theory asks: how large must a structure be to guarantee that it contains a particular ordered substructure? The simplest case is a theorem provable at a dinner party: in any group of six people, there must exist either three mutual friends or three mutual strangers. This is expressed as R(3,3) = 6 — the smallest number of vertices in a complete graph such that every two-colouring of its edges contains a monochromatic triangle. The result was proved by Frank Ramsey in 1930, in a paper motivated by questions in mathematical logic. Paul Erdős and George Szekeres extended it in 1935, proving that Ramsey numbers exist for all parameters. But knowing they exist and computing them are vastly different tasks. R(4,4) = 18 was established by Greenwood and Gleason in 1955. R(5,5) has been studied for decades and is known only to lie between 43 and 48 — with the upper bound improved from 48 to 46 by Vigleik Angeltveit and Brendan McKay in 2024. Erdős reportedly said that if an alien civilisation demanded the value of R(5,5) or they would destroy the Earth, we should marshal all our resources to compute it; but if they demanded R(6,6), we should prepare to fight. The Academy hosts Ramsey Numbers in the Mind School because the problem is pure combinatorial game theory: the search for the threshold at which chaos is no longer possible, and order must emerge.

Lineage

Frank P. Ramsey, "On a Problem of Formal Logic," Proceedings of the London Mathematical Society 30(1), 1930. Paul Erdős and George Szekeres, "A Combinatorial Problem in Geometry," Compositio Mathematica 2, 1935. R. E. Greenwood and A. M. Gleason, "Combinatorial Relations and Chromatic Graphs," Canadian Journal of Mathematics 7, 1955. The Erdős aliens quote is widely attributed; see Joel Spencer, The Probabilistic Method (Wiley, 3rd ed., 2014). Vigleik Angeltveit and Brendan McKay improved R(5,5) ≤ 46 in 2024. The broader field surveyed in Ronald Graham, Bruce Rothschild, and Joel Spencer, Ramsey Theory (Wiley, 2nd ed., 1990).

Quests

Three quests — one for each archetype. Choose the one that fits your way of taking up the discipline.

  • Write a program or carry out by hand an adversarial edge-colouring experiment for a small Ramsey problem. For R(3,3) = 6, demonstrate both sides: construct a two-colouring of K_5 that avoids monochromatic triangles, and prove that no such colouring exists for K_6. Then attempt the same for R(3,4) = 9 or R(4,4) = 18: find extremal colourings of the largest complete graph below the Ramsey number. Record your approach and what the adversarial process revealed about why larger Ramsey numbers are hard to compute.

    No attestations yetOpen →
    Sign in to claim →

  • Demonstrate the Ramsey-theoretic party problem R(3,3) = 6 with a physical or social exercise. Gather six people (or use six labelled objects) and determine, for each pair, whether they are "friends" or "strangers." Verify that among any six, three mutual friends or three mutual strangers must exist. If you can gather only five, demonstrate a colouring of K_5 that avoids a monochromatic triangle. Record the exercise and the moment the inevitability of the pattern became clear.

    No attestations yetOpen →
    Sign in to claim →

  • Explain Ramsey theory to a curious reader who knows no graph theory. Define what a Ramsey number is; prove that R(3,3) = 6 from first principles; cite Ramsey's 1930 paper, the Erdős-Szekeres 1935 improvement, and the 2023 exponential upper-bound result by Campos, Griffiths, Morris, and Sahasrabudhe. Include Erdős's aliens anecdote about R(5,5) and explain what it illustrates about the growth of Ramsey numbers.

    No attestations yetOpen →
    Sign in to claim →