A $100 question of Erdős, answered in 2026 — and the answer is no
Ramsey theory spent most of a century barely moving. The upper bound on the diagonal Ramsey number, 4ᵏ, was written down by Erdős and Szekeres in 1935. The lower bound, 2^(k/2), came from Erdős in 1947. For the next seventy-six years the exponents on both sides stayed exactly where they were, and everything published moved only the polynomial factors in front.
Then in 2023 four mathematicians broke the 4ᵏ barrier, and in 2026 a machine settled a question Erdős had put a hundred dollars on. This lesson is about what those two results actually say, and how much of the subject they leave standing. The short version of the second question is: almost all of it.
Erdős kept a list of problems with cash attached, priced by how hard he thought they were. Problem 183 asked about the k-colour triangle Ramsey number: as you add colours, does its k-th root settle down to some constant? He offered $100 for a proof that it does — a natural guess, because every lower bound anyone had ever constructed was exponential, and an exponential answer would make that root a constant.
Does R_k(3)^(1/k) tend to a finite limit as the number of colours grows?
Erdős offered the prize for a proof that it does. Every known lower bound was exponential, which would have made the limit a constant — so a finite answer was the natural guess.
R_k(3) = k^Θ(k), so the k-th root grows like k^(1/3) / log k and runs away to infinity. There is no limiting constant to find.
Drag right. At a million colours the k-th root is still only about seven, which is why an exponential answer looked believable for so long — the divergence is real but desperately slow.
R_k(3) ≥ ( (1/(6·e³⁸)) · k^(1/3) / log k )^k
That constant is about 5.23e-18, so the bracket stays below 1 — and the whole bound below 1, which is true and useless — until k reaches roughly 10^58. At k = 1000 the bound reads 10^-17,121, a number far below 1. This is a theorem about a limit, not a number you can use.
Try it: Drag the slider. The k-th root does grow without limit, but so slowly that at a million colours it has only reached about seven. That is why the finite answer looked right for so long, and why the honest headline is not a big number but a direction.
Why had the lower bound been stuck at exponential? Because the obvious way to build a big triangle-free colouring is to take one you already have, replace every vertex with a copy of the whole thing, and spend a brand new palette on the edges running between blocks. That squares the size — but it also doubles the palette, so size and colour count grow together and the answer lands at cᵏ. The 2026 construction is recursive in the same spirit and far more careful about colour, reusing one palette across many blocks at once.
Every round squares the number of vertices but spends only a few extra colours, because one palette serves many blocks at once. The structure outruns the palette, and the vertex count becomes superexponential in the colours used.
A schematic, not the proof. The published construction assembles its colourings from combinatorial designs and needs a careful argument that no triangle survives the assembly — none of which is animated here. What this does show honestly is the idea the proof turns on: growth beats the palette only if you are miserly with colour, and being miserly is what takes the answer from c^k up to k^Θ(k).
Try it: Switch between the two strategies at the same number of rounds and compare the colours spent. The vertex counts are identical; only the palette differs, and that difference is the entire theorem.
Ramsey theory has now been on the receiving end of computer proof twice, in ways that have almost nothing in common. In 2016 a SAT solver settled a colouring question about Pythagorean triples by eliminating every possibility, and emitted a certificate of two hundred terabytes that no person will ever read. In 2026 a model produced an argument, and a proof checker verified it. Both get called computer proofs. Only one of them is something a mathematician can understand.
The model produced a mathematical argument — a recursive construction assembling triangle-free colourings from combinatorial designs — and that argument was written in Lean, where a proof checker verified it line by line from the axioms.
A Lean source file in a public repository.
A mathematician can read it, and the statement at the end is a normal theorem. Machine checking removes doubt about the steps, not about whether the theorem is the right one.
Machine-checked is not the same as peer-reviewed. At announcement these results had not been through refereeing, which asks a different question: is this theorem the one that matters, and is the formal statement faithful to the informal claim?
Both of these get called computer proofs, and they sit at opposite ends of what that phrase can mean. One replaces understanding with exhaustive search and produces an artefact nobody can read. The other produces an argument in the ordinary sense and uses the machine only to check it.
Try it: Compare the last row of each panel. Machine checking removes doubt about whether the steps follow. It says nothing about whether the theorem is the one worth proving, or whether the formal statement faithfully captures the informal claim — which is what a referee is for, and what had not happened yet when these results were announced.
Both results are real and both are narrow. The 2023 work moved a base from 4 to 3.993 and later to 3.8, which is a genuine theorem and still leaves an exponentially wide gap above Erdős’s √2. The 2026 work fixed a growth rate for many colours while leaving every individual value exactly as unknown as it was.
The lower bound has stood since 1989 and the upper bound has crept down by ones. Settling it means ruling out every two-colouring of a graph on 43 or more vertices, and there are more of those than any conceivable computation could enumerate. Erdős’s remark was that if aliens demanded R(5,5) we should put every mathematician and computer on Earth onto it, and if they demanded R(6,6) we should fight them instead.
| k | R(k,k) |
|---|---|
| 3 | 6 |
| 4 | 18 |
| 5 | 43 – 46 |
| 6 | 102 – 165 |
| 7 | 205 – 492 |
Nine decades after Ramsey, 2 diagonal values are known — R(3,3) = 6 and R(4,4) = 18 — along with a handful of off-diagonal ones and exactly 2 multicolour values. Everything else is a range.
Frank Ramsey proved his theorem in 1930 and died later that year, aged twenty-six, having written it as a lemma on the way to something else. The subject that grew out of that lemma has since produced one of the most quotable facts in mathematics — complete disorder is impossible — and one of the most stubborn: we do not know how many people must come to a party before five of them are guaranteed to be mutual friends or mutual strangers, and the answer is one of only four numbers.
What changed in the last three years is not that the problem became easy. It is that two of its bounds moved at all, after decades in which nothing did — once because four people found a better way to grow a book, and once because a machine was pointed at a question with a hundred dollars on it and answered no. The same thing happened to sphere packing in the same window, with the human and the machine working on opposite sides of the gap. Whether that is a coincidence or the beginning of something is not yet a mathematical question.