Order is unavoidable — every large enough structure contains the pattern you were avoiding
Fix two targets: a red clique on s vertices and a blue clique on t. Ramsey’s theorem says there is a finite number R(s, t) such that every red/blue colouring of the edges of the complete graph on that many vertices contains one or the other. Not most colourings. Every colouring, including the ones designed by someone who has read the proof.
It is worth pausing on how strange that is. A colouring of K₁₈ is one of 2¹⁵³ objects — a 47-digit number of them — and the claim is that not a single one of them avoids both a red K₄ and a blue K₄. You cannot verify this by being clever about the colourings you happen to think of. You have to rule out all of them at once, and the graphs get bigger without limit as s and t grow, so there are infinitely many such claims to establish.
Frank Ramsey proved it in 1930, in a paper about formal logic, where the combinatorial statement appears as a lemma on the way to something else. He died later that year, aged 26, and never saw a single value of his function computed.
The theorem hands you a grid of finite numbers and refuses to say what any of them are. Ninety-five years later the grid is still almost empty. The values we have came from finite fields, from computations that ran for years, and from arguments tailored to one cell at a time — and they stop, abruptly, almost as soon as they start.
| s \ t | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 2 | |||||||||
| 3 | |||||||||
| 4 | |||||||||
| 5 | |||||||||
| 6 | |||||||||
| 7 | |||||||||
| 8 | |||||||||
| 9 | |||||||||
| 10 |
4 candidate values remain; the upper bound is 1.07× the lower.
Lower bound Exoo 1989; upper bound Angeltveit and McKay
Of the 64 non-trivial pairs shown, exactly 16 have a known value. Every one of them sits in the top-left corner, and the whole table is symmetric because swapping the two colours swaps s and t. Ramsey’s theorem says each of these cells holds a finite number. It says nothing about which.
Try it: Tap any cell for its provenance. Walk down the first row — R(3, t) is known out to t = 9 and then stops. Walk down the diagonal and it stops at R(4,4). Every open cell is a bracket rather than a number, and the shaded bar inside it is how wide the bracket is: by R(8,8) the upper bound is more than five times the lower.
In 1935 Paul Erdős and George Szekeres found the argument that everyone still uses, and it is almost embarrassingly short. Suppose you already know R(s−1, t) and R(s, t−1). Take a graph on R(s−1, t) + R(s, t−1) vertices, coloured however you like, and pick any vertex v. Every other vertex is joined to v by exactly one edge, red or blue, so the rest of the graph splits into two piles. The two piles have one fewer vertex between them than the two thresholds add up to, which means they cannot both fall short. One of them is big enough to be a smaller Ramsey problem, and the smaller problem hands back a clique that either finishes the job or grows by one when you attach v.
Notice what the argument never does: it never looks at an edge that does not touch v. All of the structure in the colouring, all 2 raised to the edge count of it, is thrown away in favour of a single vertex and a pigeonhole.
A complete graph, every edge coloured
Every one of the 190 edges is red or blue, chosen by an adversary who wants no red K₄ and no blue K₄. We never look at most of them.
Try it: Step to the pigeonhole and drag the red degree across its whole range. One side is always at or above its threshold — you cannot find a split that defeats both, because the two thresholds sum to one more than the number of vertices you have to distribute. That impossibility is the entire proof.
The recursion R(s, t) ≤ R(s−1, t) + R(s, t−1) is Pascal’s rule wearing a disguise. Start it from the free case R(2, t) = t — a red clique on two vertices is just a red edge — and unwind, and you land exactly on a binomial coefficient: R(s, t) ≤ C(s + t − 2, s − 1). On the diagonal that is the central binomial coefficient C(2k − 2, k − 1), which sits comfortably below 4ᵏ. So R(k,k) < 4ᵏ, and the number of vertices you need grows at most exponentially.
That bound was published in 1935. Its exponential base was not improved for 88 years. Constants in front of it moved, logarithmic factors were shaved off the top, but 4ᵏ stood until 2023 — which tells you that the one-vertex argument, wasteful as it looks, is capturing something real.
Every cell of the triangle is an Erdős–Szekeres bound. The second diagonal, all the 1, 2, 3, 4 …, is the base case R(2,t) = t; Pascal’s rule is the induction.
The central binomial coefficient is about 14.6× smaller than 45 here, and the ratio grows like √k. So R(k,k) < 4k is a genuine round-down — the shape of the bound, not the constant, is what mattered.
By k = 100 the bound says R(100,100) is at most a 59-digit number. Nobody has ever computed a Ramsey number past the single digits of k, and the honest gap between what this bound permits and what is known is the whole subject.
Try it: Hover any cell to see which Ramsey number it bounds — the triangle is a complete table of the 1935 result. The second diagonal, 1, 2, 3, 4 …, is the base case R(2,t) = t, and the two coloured edges into the highlighted cell are the two halves of the pigeonhole.
Ramsey’s theorem is an existence statement, and existence statements are cheaper than they look. Knowing that R(5,5) is finite tells you a search terminates. It does not tell you where, and the search in question is over every two-colouring of a graph with hundreds of edges. The largest graph anyone can two-colour without producing a monochromatic K₅ has 42 vertices and 861 edges — and it admits more colourings than there are atoms in the observable universe, cubed.
Meanwhile the bounds we can actually prove are 2^(k/2) below and 4ᵏ above — a band whose two ends differ by a factor that itself grows exponentially. The gap has been open since Erdős produced the lower bound in half a page of probability in 1947. Closing it — even deciding which end is closer to the truth — is one of the oldest open problems in combinatorics.
Ramsey’s theorem promises this search halts. That is genuinely all it promises, and the promise is worth less than it sounds: the search is finite in the same sense that counting to 1.54 × 10259 is finite. Quotienting by symmetry does not rescue it either — there are only about n! relabellings to divide out, a rounding error against 2 raised to the edge count.
Try it: Drag k up and watch the solid bar — everything actually known — vanish inside the pale band of what is merely provable. Then read the brute-force figure underneath. At k = 3 it is 1,024 colourings, which a laptop clears instantly. At k = 5 it is past 10250.
In March 2023 Marcelo Campos, Simon Griffiths, Robert Morris and Julian Sahasrabudhe proved R(k,k) ≤ 3.993ᵏ, the first improvement to the exponential base since Erdős and Szekeres. Their argument replaces the single vertex with a structure called a book, and it is long where the 1935 proof is short. A year later the base came down again, to about 3.8. The lower bound is still √2 to the k, exactly where 1947 left it — so the record that moved was the one nobody expected to, and the small values remain as stubborn as ever.