Pith. sign in

REVIEW 4 major objections 3 minor 10 references

Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe]

T0 review · 4 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For the first time since 1935, the upper bound on the diagonal Ramsey number has been pushed below $4^k$, and this survey explains both proofs.

desk verdict A genuinely useful Bourbaki survey with a real but localized bug in the proof of the geometric lemma—worth fixing, not rejecting. read the letter →

arxiv 2411.09321 v2 pith:KFGHBHPW submitted 2024-11-14 math.CO

Yuval Wigderson This is my paper · ORCID
classification math.CO MSC 05D1005C55
keywords diagonalRamseynumbersupperboundsbookalgorithmgraphstheoryrefinementlemmageometricmulticolor
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This survey explains a 90-year-old breakthrough: the diagonal Ramsey number $r(k)$, the least $N$ such that every red/blue coloring of the edges of $K_N$ contains a monochromatic $K_k$, is at most $(4-\delta)^k$ for some constant $\delta>0$, concretely $3.993^k$ for large $k$. The first proof route, the book algorithm, is presented as a refined version of the Erdős–Szekeres argument, and the survey shows exactly why the naive version stalls near $4.15^k$ before two corrections bring it below $4$. The second route, due to a later group, is more symmetric and rests on a geometric lemma about correlations of random vectors; it yields $r(k) \le 2^{(2-\eta^2/10)k}$ with $\eta=1/8000$. The survey is explicit that its sketches rely on regularity assumptions it calls bogus and that a rigorous proof needs a cleaning step that is not carried out here.

What carries the argument

The load-bearing object is the monochromatic book graph $B_{t,m}$: a $K_t$ spine with $m$ pages, all connected to the spine. Both proofs grow such books through an algorithm that moves vertices between sets $A,B,X,Y$ (and $Z$ in the symmetric proof) and tracks how the sizes and the red/blue densities evolve; the step-by-step parameter tables are what convert the algorithm into a bound on $N$. In the symmetric proof the crucial mechanism is the refinement lemma, proved by a geometric argument: centered indicator vectors of red and blue neighborhoods are fed into the function $f(y,z)=1+y(2+\cosh\sqrt{2z})+z(2+\cosh\sqrt{2y})$, chosen so that all Taylor coefficients are nonnegative, so the expectation of $f$ over independent random vertices is at least $1$; the lemma then converts a large value of $f$ into a simultaneous lower bound on the two inner products. The quadratic dependence of the density boost on $\kappa$ is what makes the density-boost steps negligible in the final bookkeeping.

What would settle it

A direct way to test the central claim is to search for a two-coloring of $K_N$ with $N = 3.994^k$ and no monochromatic $K_k$; any such coloring for even one large $k$ would falsify the bound. Short of that, the proof mechanism can be tested by simulating the book algorithm on colorings whose red degrees between $X$ and $Y$ are deliberately non-regular: if the cleaning step cannot restore approximate regularity without shrinking $Y$ by more than $2^{-o(k)}$, the parameter tables in the survey no longer support the claimed conclusion.

Watch

Extended reading notes

Core claim

The central claim, stated on the paper's own terms, is that $r(k) \le (4-\delta)^k$ is a theorem and that both known proofs are sound in structure: the book algorithm of the 2023 proof and the symmetric book algorithm of the later proof. The first proof maintains a red book $(A,Y)$ and a blue book $(B,X)$, sacrificing $X$ to build $Y$; its success reduces to a numerical maximum of two functions $F$ and $G$, and the missing margin is supplied by an off-diagonal bound $r(k,\ell) \le 2^{-2\ell/9+o(k)}\binom{k+\ell}{\ell}$ for $\ell \le k/4$. The second proof adds a third set $Z$ and applies a refinement lemma that, for any two families of vectors, finds a vertex whose red and blue neighborhoods have a large simultaneous correlation; the density boost from this lemma is quadratic in the shrinkage parameter, which is exactly what makes the parameter tracking close. The survey presents both proofs as sketches and repeatedly flags that the regularity assumptions used to write the parameter tables are unjustified as stated.

Load-bearing premise

The load-bearing premise is that at every step the red edges between $X$ and $Y$ are exactly regular, meaning every vertex in $X$ has the same number $p|Y|$ of red neighbors in $Y$ and every vertex in $Y$ has the same number $p|X|$ of red neighbors in $X$. The survey calls this assumption completely unjustified and bogus, and says that a cleaning step deleting outlier vertices can make it approximately true, but the cleaning is never actually proved.

Editorial extensions

If this is right

  • The exponential growth rate of $r(k)$ is strictly below the base $4$, so the Erdős–Szekeres constant is not the asymptotic truth.
  • For $\ell \le k/4$, the off-diagonal bound improves the binomial estimate by an exponential factor $2^{-2\ell/9+o(k)}$, which is the ingredient that closes the gap in the diagonal argument.
  • The symmetric proof extends to multicolour Ramsey numbers, giving new upper bounds for any fixed number of colors.
  • Because the book algorithm either finds a monochromatic $K_k$ or produces a book whose parameters force one, the proof is in principle algorithmic.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The unproved cleaning step is the most delicate point to formalize: any cleaning that shrinks $Y$ by more than $2^{-o(k)}$ between steps would degrade the constant below $3.993$.
  • A polynomial strengthening of the geometric lemma, where only an exponential bound is currently known, would likely improve the exponent in the final bound, since the present proof loses a factor $e^{-4\kappa}$ in the probability estimate.
  • The numerical-inequality route invites a computational search over the cutoff $\mu$; the paper notes that optimizing the constants yields substantially stronger bounds, so a systematic optimization could push the base below the current values.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. This Bourbaki survey presents the history of upper bounds on diagonal Ramsey numbers and explains the recent breakthrough of Campos, Griffiths, Morris, and Sahasrabudhe that r(k) ≤ (4−δ)^k, together with the later alternative proof by Balister et al. The paper gives three views of the Erdős–Szekeres bound, introduces the book algorithm with density-boost steps, sketches the off-diagonal refinement that yields r(k) ≤ 2^{(2−3/200+o(1))k}, and then describes the symmetric book algorithm of Balister et al., whose key refinement lemma is reduced to a high-dimensional geometric statement about inner products. The exposition is explicitly conditional: Assumptions 3.1, 4.4, 5.1, and 5.2 are admitted to be unjustified, and several numerical inequalities are verified by plots rather than rigorous computations.

Significance. If the proofs were correct, this would be a valuable and readable account of a major recent development in Ramsey theory. The paper is unusually honest about which parts are rigorous and which are sketches; the proof of the Erdős–Szekeres theorem, the one-color geometric lemma (Proposition 6.3), and Ramsey's book proof are clean and self-contained. The survey also gives useful context, including Thomason's conjecture and Conlon's theorem on book Ramsey numbers. However, the proof of the central geometric lemma contains a false statement, and the main theorems of Sections 4 and 5 are derived under assumptions that the paper itself labels bogus. As a result, the survey's account of the new proofs is not correct as written.

major comments (4)
  1. [Section 6.3, Lemma 6.7] The asserted non-positivity of f is false. For y = −1 and z = 1, f(−1,1) = 1 − (2 + cosh(√2)) + (2 + cosh(√2)) = 1, which is positive. The proof of Theorem 6.2 uses this non-positivity to conclude that V is non-positive on the complement of E and hence E[V 1_E] ≤ 0. With f(−1,1) > 0, that conclusion is unjustified, and the derivation of the key estimate (6.11) collapses. This is not one of the explicitly flagged 'bogus' assumptions; it is presented as a calculus exercise. The lemma must be corrected or the proof of Theorem 6.2 must be supplied by a different argument, since this is the load-bearing step in the presented proof of the refinement lemma and hence of Theorem 5.11.
  2. [Sections 3–5, Assumptions 3.1, 4.4, 5.1, 5.2] The derivations of Theorems 4.6, 4.7, and 5.11 depend on the bi-regularity and initial-density assumptions that the paper itself describes as 'bogus' and 'completely unjustified.' The promised cleaning argument is never given. For example, Lemma 4.5 and the proof of Theorem 4.6 rely on |Y| ≥ (1−μ)^{t+s+o(k)}N, which in turn requires that blue steps keep p constant and that red steps shrink Y by a factor of p; both facts are consequences of Assumption 3.1. In an expository survey, a clearly labeled conditional sketch would be acceptable, but the paper states Theorem 4.7 as a theorem and Theorem 5.11 as a proof, with only parenthetical remarks saying the proof is incomplete. Please either supply or cite the exact cleaning argument from the original papers, or restate the central theorems as conditional on these assumptions.
  3. [Section 6.1, proof of Lemma 5.3] The proof of Lemma 5.3 uses the identity |Y'| = p_R|Y| and the analogous identity for Z, citing Assumption 5.1. However, Lemma 5.3 is stated without that assumption, and Lemma 6.1 is also stated as a general statement about arbitrary sets X,Y,Z in a coloring. Thus Lemma 5.3 is not proved as stated; it is proved only under an additional regularity hypothesis that is not part of the lemma's hypotheses. Either the lemmas should be stated with the required regularity assumptions explicitly included, or a proof without those assumptions should be supplied.
  4. [Section 5.2, Algorithm 5.4, step 4(a)] Step 4(a) says to perform a red density-boost step if d_R(X',Y') ≥ (κ^2−1)p_R, but Lemma 5.3(c) and Table 5.1 require the condition d_R(X',Y') ≥ p_R + (κ^2−1)α_R. As written, the algorithm's condition is inconsistent with the later analysis: for large κ, (κ^2−1)p_R can be much larger than p_R, and the stated update rule would not follow from the refinement lemma. This appears to be a typo, but it is load-bearing because the subsequent Lemma 5.9 uses the density increase guaranteed by the correct condition.
minor comments (3)
  1. [Section 5.4, proof of Theorem 5.11] The final sentence says the coloring contains a monochromatic K_t, but Lemma 2.4 with m = r(k−t,k) produces a monochromatic K_k; the displayed bound is for r(k), so 'K_t' should be 'K_k'.
  2. [Section 4.3, Theorem 4.7] The numerical verification that max min{F̂, G_{2/5}} < 0.985 is presented via contour plots. For a survey this may be acceptable, but the theorem is stated with a definite numerical constant; a reference to the rigorous computation in the original papers would make the claim verifiable.
  3. [Section 2.3, Algorithm 2.6] The claim that this recovers Theorem 2.2 'up to the subexponential error term' is slightly loose, since the bound obtained is N < (1−γ)^{−k}γ^{−ℓ}, which matches (k+ℓ choose ℓ) only up to polynomial factors; the statement could be made more precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the survey is a self-contained exposition that attributes each central theorem to the original papers and uses self-citations only as background references.

full rationale

This paper is an expository survey. Its central claims (Theorems 1.5, 4.6, 4.7, and 5.11) are explicitly attributed to Campos-Griffiths-Morris-Sahasrabudhe (2023), Gupta-Ndiaye-Norin-Wei (2024), and Balister et al. (2024), and the survey repeatedly warns that its own presentation is a sketch. The 'bogus' Assumptions 3.1, 4.4, 5.1, and 5.2 are flagged by the author as unjustified simplifications; they are limitations of the exposition, not inputs that secretly define the outputs. The self-citations (Wigderson 2024 lecture notes and Conlon-Fox-Wigderson 2022) are background references and do not carry any load-bearing argument; no uniqueness theorem from the author's own prior work is invoked to force a conclusion. The derivation of Lemma 5.3 from Lemmas 6.1, Theorem 6.2, and Lemma 6.7 is mathematical and self-contained in structure, with no fitted parameter renamed as a prediction and no result quoted from the same authors as a substitute for proof. The skeptical observation that Lemma 6.7's non-positivity claim appears false (e.g., f(-1,1)=1) is a potential correctness defect in the presented proof, but it is not circularity: the claimed theorem is still attributed to Balister et al., and the flawed lemma is not an input that is equivalent to the desired outcome by construction. Accordingly, no circular step meets the evidentiary standard required by the task.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The proofs in this survey rest on five hand-chosen parameters, ε, μ, η, κ_cutoff, and two numerically certified constants, and on four unjustified regularity assumptions that the author explicitly labels 'bogus' or 'not justified'. These assumptions are not data-fit; they are simplifying hypotheses for exposition. The paper states that real proofs remove them via deletion arguments, but does not carry those out. This is the honest measure of the survey's contents: the theorems are imported from the cited literature, and the expository derivations are conditional on the assumptions above.

free parameters (5)
  • ε = k^{-1/4} (t^{-1/4} in the symmetric algorithm)
    Chosen by hand in §3.3 to balance the density drop from red steps against the total number of steps. The author notes many other choices would work, so it is a proof parameter, not fitted to data.
  • μ (blue-step cutoff) = 2/5 in the diagonal proof; ℓ/(k+ℓ) in the off-diagonal proof
    Selected in §4.1–§4.3 to shrink the bad region where min{F,G_μ} exceeds 1. No single μ below 1 works, so the off-diagonal refinement is needed; μ = 2/5 is the eventual diagonal choice.
  • η and κ_cutoff = η = 1/8000, κ_cutoff = 400
    Chosen in §5.2 to satisfy the four inequalities before Algorithm 5.4, namely κ_cutoff ≥ 8C, κ_cutoff² ≥ 8 log2(1/c), 2(log2(1/c)+Cκ_cutoff)+5 < 1/η, and κ_cutoff² ≥ 20/η. The author states no optimization was attempted.
  • Numerical slack 2/9 = δ = 2/9 in Theorem 4.6
    The claimed gain in the off-diagonal bound is verified by contour plots in §4.2 ('one can check that for μ ≤ 1/5, we may take δ as large as 2/9'); no rigorous inequality proof is given in the paper.
  • Numerical slack 3/200 = 1 − 0.985 = 3/200 in Theorem 4.7
    The proof needs max min{F̂,G_{2/5}} < 0.985; the author states 'one can check' this from plots and calls the computation 'proving through pictures' (§4.3).
assumptions (5)
  • ad hoc to paper Assumption 3.1: at every step, red edges between X and Y form a bi-regular bipartite graph: each vertex in X has exactly p|Y| red neighbors in Y and each vertex in Y has exactly p|X| red neighbors in X.
    Called 'a completely unjustified assumption' and 'bogus' in §3. It is used in the derivations of Lemma 3.3, Lemma 3.4, inequality (3.1), Lemma 3.6, and Table 3.1. The author asserts a cleaning argument can make it essentially rigorous but gives no details.
  • ad hoc to paper Assumption 4.4: at the start of the off-diagonal book algorithm, the initial red density p_initial between X and Y is at least k/(k+ℓ) = 1 − μ.
    Called 'completely unjustified' in §4.2. The author sketches how Erdős-Szekeres steps could force it, but the reduction is not written out. Lemma 4.5 and Theorem 4.6 depend on this assumption.
  • ad hoc to paper Assumptions 5.1 and 5.2: every vertex in X has exactly p_R|Y| red neighbors in Y and p_B|Z| blue neighbors in Z; initially p_R ≥ 1/2 and p_B ≥ 1/2.
    Stated in §5.1; in §5.4 the author says the proof 'is not complete, as it relies on Assumptions 5.1 and 5.2'. They are used to derive |Y'| = p_R|Y| and |Z'| = p_B|Z| and to justify Table 5.1.
  • ad hoc to paper The numerical inequalities on the auxiliary functions F, G_μ, F̂, ~F, ~G are correct as stated, e.g., max min{F,G_{2/5}} < 0.985 and the slack 2/9 for μ ≤ 1/5.
    These inequalities carry the final constants in Theorems 4.6 and 4.7 and are verified by contour plots, not formal proofs. The paper concedes 'we content ourselves with proving the numerical bounds through pictures' (§4.3).
  • standard math Stirling's approximation and the binary entropy bound: binomial coefficient (a choose b) ≤ 2^{a H(b/a)}.
    Used in §2.3 and §4 to convert binomial coefficients into exponential bounds. Standard and unproblematic.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe]." pith.science (2026). https://pith.science/paper/KFGHBHPW

@misc{pith2026241109321,
  author       = {Pith},
  title        = {Pith review of: Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe]},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KFGHBHPW}},
  note         = {Machine review of arXiv:2411.09321}
}
abstract

Ramsey's theorem states that if $N$ is sufficiently large, then no matter how one colors the edges among $N$ vertices with two colors, there are always $k$ vertices spanning edges in only one color. Given this theorem, it is natural to ask ``how large is sufficiently large?'' Ramsey's original proof showed that $N=k!$ is sufficient, and five years later Erd\H{o}s and Szekeres improved this bound to $N=4^k$. And then progress stalled for almost 90 years. In this survey, I present the history of the problem and discuss some of the ideas used in the recent breakthrough of Campos--Griffiths--Morris--Sahasrabudhe, who proved that $N=3.993^k$ is sufficient. In addition, I discuss the subsequent work of Balister, Bollob\'as, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba, who gave an alternative, and more conceptual, proof.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 7 canonical work pages

  1. [1]

    McKay (2024).R(5,

    Vigleik Angeltveit and Brendan D. McKay (2024).R(5,

    work page 2024

  2. [10]

    A new upper bound for diagonal Ramsey numbers

    Colloq. Math. Soc. János Bolyai. North-Holland, Amsterdam-London, pp. 215–240. Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe (2023).An exponential improvement for diagonal Ramsey. arXiv: 2303.09521 [math.CO]. David Conlon (2009). “A new upper bound for diagonal Ramsey numbers”,Ann. of Math. (2)170(2), pp. 941–960. (2019). “The Ra...

    arXiv 2023

  3. [46]

    On the magnitude of generalized Ramsey numbers for graphs

    arXiv: 2409.15709 [math.CO]. Paul Balister, Béla Bollobás, Marcelo Campos, Simon Griffiths, Eoin Hurley, Robert Morris, Julian Sahasrabudhe, and Marius Tiba (2024).Upper bounds for multicolour Ramsey numbers. arXiv: 2410.17197 [math.CO]. Thomas F. Bloom and Olof Sisask (2020).Breaking the logarithmic barrier in Roth’s theorem on arithmetic progressions. a...

    arXiv 2024

  4. [64]

    Regular partitions of graphs

    CBMS-NSF Re- gional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, pp. vi+88. Endre Szemerédi (1978). “Regular partitions of graphs”, in:Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Vol

    work page 1978

  5. [109]

    Diagonal Ramsey via effective quasirandomness

    Ashwin Sah (2023). “Diagonal Ramsey via effective quasirandomness”,Duke Math. J. 172(3), pp. 545–567. Issai Schur (1917). “Über die Kongruenzxm +ym≡ zm (mod p)”, Jahresber. Dtsch. Math.-Ver.25, pp. 114–117. Joel Spencer (1975). “Ramsey’s theorem—a new lower bound”,J. Combin. Theory Ser. A 18, pp. 108–115. (1994). Ten lectures on the probabilistic method. ...

    work page 2023

  6. [123]

    The primes contain arbitrarily long arithmetic progressions

    London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, pp. 111–153. Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer (1990).Ramsey theory. 2nd ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley- Interscience Publication. John Wiley & Sons, Inc., New York, pp. xii+196. Ben Green and Terence Tao (2008). ...

    arXiv 1990

  7. [260]

    On finite Ramsey numbers

    Colloq. Internat. CNRS. CNRS, Paris, pp. 399–401. Andrew Thomason (1982). “On finite Ramsey numbers”,European J. Combin.3(3), pp. 263–273. (1988). “An upper bound for some Ramsey numbers”,J. Graph Theory12(4), pp. 509–517. Johannes G. van der Corput (1939). “Über Summen von Primzahlen und Primzahl- quadraten”, Math. Ann.116(1), pp. 1–50. Yuval Wigderson (...

    work page 1982

  8. [424]

    Ramsey numbers of books and quasirandomness

    London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, pp. 49–118. David Conlon, Jacob Fox, and Yuval Wigderson (2022). “Ramsey numbers of books and quasirandomness”,Combinatorica 42(3), pp. 309–363. Paul Erdős (1947). “Some remarks on the theory of graphs”,Bull. Amer. Math. Soc. 53, pp. 292–294. Paul Erdős, Ralph J. Faudree, Cecil C. Rouss...

    work page 2022

Show all 10 references
  1. [2023]

    The asymptotics ofr(4,t )

    IEEE Computer Soc., Los Alamitos, CA, pp. 1271–1281. Sam Mattheus and Jacques Verstraete (2024). “The asymptotics ofr(4,t )”, Ann. of Math. (2)199(2), pp. 919–941. 1230–48 Sarah Peluse (2022). “Recent progress on bounds for sets with no three terms in arith- metic progression”...

    2024

  2. [2308]

    On certain sets of integers

    15589 [math.CO]. Klaus F. Roth (1953). “On certain sets of integers”,J. London Math. Soc.28, pp. 104–

    1953

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.