The 2023 result that moved a bound nobody had improved since 1935
In 1935 Erdős and Szekeres proved that R(k,k) < 4ᵏ. In 1947 Erdős proved that R(k,k) > 2^(k/2). Between those two statements sits a gap of an exponential factor, and for the next eighty-eight years the base on neither side moved. Not once. People improved the polynomial in front — five times, by increasingly clever arguments — but the number being raised to the power k stayed at 4 above and √2 below.
In March 2023, Marcelo Campos, Simon Griffiths, Robert Morris and Julian Sahasrabudhe posted a paper proving R(k,k) ≤ (4 − ε)ᵏ, with ε = 2⁻⁷. That is 3.993ᵏ. The improvement is 0.175% of the base and it was the biggest news in combinatorics in a decade, because what changed was not a bound but a rate.
The classical argument builds a monochromatic clique one vertex at a time: pick a vertex, keep its red neighbours, repeat. Every step throws away roughly half the graph, and the factor of 2 per step is precisely where the 4ᵏ comes from. The 2023 proof grows a different object. A book is a red clique — the spine — together with a set of vertices, the pages, every one of which is joined in red to the entire spine. Books are cheaper to grow than cliques and they carry more information: the page set remembers how red the remaining graph is.
Each step promotes one page onto the spine and throws away every vertex not joined to it in red. Roughly a 50% fraction of the pages survives, so the page count decays geometrically and the spine reaches about log(N)/log(1/0.50) ≈ 7 vertices. Push the red fraction up and the spine grows sharply — which is the entire reason the real algorithm works so hard to keep the density high.
This is a schematic, not the proof. The real book algorithm of Campos, Griffiths, Morris and Sahasrabudhe interleaves steps of this kind with two others: a blue step, taken when the chosen vertex has too few red neighbours, and a density-boost step that deliberately discards part of the page set to raise the red density inside it. The 4ᵏ → 3.993ᵏ saving comes entirely from proving that the density can be made to drift upward faster than the blue steps waste it, on an adversarial colouring rather than a random one. Nothing on this screen establishes that; it only shows you the object the argument is about.
Try it: Press Play and watch the page count fall by roughly the red fraction at every step. Then drag the red fraction to 70% and rebuild. The spine gets dramatically longer for the same 160 vertices — which is the whole reason the real algorithm fights so hard to keep the density of the remaining graph high.
The 1935 bound is not a clever argument that happened to be hard to beat. It is the obvious argument, and every improvement before 2023 attacked the same quantity in the same place. Thomason in 1986 removed a power of k. Conlon in 2009 removed more than any power of k. Sah in 2020 pushed that method to what looked like its ceiling. Every one of those results is a real theorem and every one of them leaves the k-th root of the bound converging to exactly 4.
| Year | Bound | Saving over 4ᵏ | k-th root |
|---|---|---|---|
| 1935 | R(k,k) ≤ C(2k−2, k−1) | about √k | 4 |
| 1986 | R(k,k) ≤ k^(−1/2+o(1)) · 4ᵏ | polynomial in k | 4 |
| 2009 | R(k,k) ≤ k^(−c·log k / log log k) · 4ᵏ | superpolynomial, still subexponential | 4 |
| 2020 | R(k,k) ≤ e^(−c·(log k)²) · 4ᵏ | quasi-polynomial | 4 |
| 2023 | R(k,k) ≤ (4 − ε)ᵏ, ε = 2⁻⁷ | a fraction of the exponent | ≤ 3.993 |
| 2024 | R(k,k) ≤ 3.8^(k+o(k)) | more of the exponent | ≤ 3.8 |
The book algorithm. Instead of extending a clique one vertex at a time, it grows a book — a clique together with a whole set of vertices joined to all of it — and the accounting of how the red density drifts as the book grows is what buys a constant off the base. It is the first change to the exponential rate since 1935.
One curve on that chart is exact: the k-th root of the 1935 binomial coefficient, which climbs towards 4 and never reaches it. Everything proven between 1986 and 2020 sits somewhere in the shaded sliver underneath — below 4ᵏ, with the same limit — and none of those curves is drawn, because the constants inside them were never specified and any plot would be an invention. Note where the dots sit: the old binomial bound is numerically smaller than 3.8ᵏ until k ≈ 81 and smaller than 3.993ᵏ until k ≈ 3,443. The 2023 theorem is an asymptotic statement, and for every k anyone will ever compute with, the 1935 bound is still the better number. What changed is the rate.
Try it: Click through the six rows and watch the right-hand column. It reads 4, 4, 4, 4 — and then changes. The two dots on the chart mark where the 1935 bound is finally overtaken numerically, which does not happen until k is in the thousands: the 2023 theorem is about the rate, not about any k you could compute with.
Two ways of describing the same theorem, both true. One: the base fell from 4 to 3.993, a change of under a fifth of one per cent, and if you write both bounds out at k = 1,000 they have the same number of digits to within one. Two: the new bound is smaller than the old one by a factor of (4/3.993)ᵏ, which grows exponentially and passes a googol before k reaches 132,000. The second framing is why the result matters; the first is why it took so long to be possible.
The base fell by 0.175%. On this picture the 2023 theorem of Campos, Griffiths, Morris and Sahasrabudhe is almost invisible.
The factor reaches 10 at k = 1,315.
The factor reaches 10⁶ at k = 7,888.
The factor reaches 10¹⁰⁰ at k = 131,462.
Both framings are true and neither is the whole story. Shaving 0.175% off the base is, at k = 1,000, worth a factor of about 5.8 — you would not notice it in the digit count. But the factor is (4/3.993)ᵏ, and an exponential in k does not stay small: by k = 131,462 it exceeds a googol. That is the difference between improving a bound and changing its rate, and it is the reason a theorem worth 0.175% took eighty-eight years and a new algorithm.
Try it: Switch between the 2023 and 2024 bases. The bar chart barely notices the difference between 3.993 and 3.8; the slope of the ratio line changes by a factor of twenty-nine. Nothing on the page is ever exponentiated — every quantity is held as a base-10 logarithm, because 4ᵏ at k = 100,000 has 60,206 digits.
It would be a mistake to read the breakthrough as closing the problem. The lower bound is still Erdős’s from 1947, √2 ≈ 1.414 per step; the upper bound is now 3.8. Those are different numbers, so the two bounds differ by an exponentially growing factor and always have. What the true growth rate is — even whether R(k,k)^(1/k) converges at all — remains one of the most famous open questions in combinatorics. Erdős offered $100 for a proof that the limit exists and $250 for its value. Both are unclaimed.
At k = 40 the two sides differ by a factor of 1.48 × 10¹⁷. The breakthrough moved the upper bound down by a factor of 1.1, and the 2024 refinement by 7.8 — real progress, and nowhere near enough to reach the blue line.
Every bound here is exponential in k, so on a logarithmic axis they are all straight lines and the only thing that distinguishes them is the slope. That is why 4ᵏ and 3.993ᵏ are drawn on top of each other: their slopes differ in the fourth decimal place. The honest summary is the shaded wedge. Erdős offered $100 for a proof that lim R(k,k)^(1/k) exists at all, and $250 for its value. Ninety years on, nobody knows whether the limit exists; all that is proven is that it would have to lie between √2 ≈ 1.414 and 3.8. Both prizes stand.
Try it: Set the range to 20 and the white bars show everything that is genuinely known about the diagonal — a handful of values, tiny against the wedge. Then push the range to 1,000 and read the gap factor. It is a number with hundreds of digits, and closing it is the actual problem.
Within a year, Gupta, Ndiaye, Norin and Wei tuned the parameters of the book algorithm and brought the bound to 3.8^(k+o(k)). That is the usual pattern: the hard part is showing that the barrier is not real, and once it is gone the constant becomes an optimisation problem. The same story is playing out in the multicolour problem and in sphere packing, where a bound untouched since 1978 moved in 2026. Barriers in combinatorics tend to be failures of technique rather than facts about the answer — and the only way to tell the difference is for somebody to get past one.