What Is a Ramsey Number?

Invite enough people to a party, and among any group that large, you’re guaranteed to find either a clique of mutual acquaintances or a clique of mutual strangers of a certain size — no matter how the acquaintances happen to be arranged. The Ramsey number R(m, n) is the exact smallest party size where that guarantee kicks in for a clique of m acquaintances or n strangers.

A concrete, solved example

R(3, 3) = 6 is the classic version: at any party of 6 people, there must be either 3 mutual acquaintances or 3 mutual strangers. At a party of only 5, you can arrange things to avoid both — so 6 is exact, not just an upper bound.

Two other exact values are known: R(4,4) = 18, proved by Greenwood and Gleason in 1955, and R(4,5) = 25, proved by McKay and Radziszowski in 1995 and, in 2024, independently re-verified inside the HOL4 formal proof assistant — a machine-checked confirmation of a decades-old human proof.

Why R(5,5) is the famous unknown one

R(5,5) is not known exactly. The best current bounds, from the standard reference (Radziszowski’s dynamic survey Small Ramsey Numbers), are 43 ≤ R(5,5) ≤ 46. The lower bound of 43 has stood since 1989; the upper bound was 49 as of 1997, tightened to 48 in 2016, and tightened again to 46 in a 2024 paper by Angeltveit and McKay. There’s a standing conjecture — not a proof — that the true value is exactly 43. See the full record at LR-RAMSEY-5-5.

Paul Erdős is often quoted describing the difficulty: even with every computer on Earth working on it, determining R(5,5) exactly might be beyond reach before an alien invasion forces a faster answer by less peaceful means — humorous, but a genuine reflection of how badly brute-force search scales here. The number of ways to 2-color the edges of a graph on just 45 vertices vastly exceeds the number of atoms in the observable universe.

Why it’s hard

Ramsey numbers grow explosively, and there’s no known formula — each one has essentially had to be pinned down by a combination of clever combinatorial constructions (for the lower bound) and increasingly heavy computer search (for the upper bound). Proving an exact value means closing the gap from both directions at once, and for R(5,5), that gap has taken 35 years to shrink from 7 to 3.

Why it’s here

Ramsey numbers are a case where “we don’t know the exact answer” is itself a precise, well-defined, actively narrowing fact — exactly what a bound frontier is supposed to capture, rather than a vague open question with no measurable progress.