REVIEW 3 major objections 3 minor 18 references
Polynomial-to-exponential transition in 3-uniform Ramsey numbers
T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read The paper proves that for every fixed $s>3$, the 3-uniform Ramsey number $r_3(s, g_3(s)+1; t)$ is exponential in $t^{2/3}$, completing the Erdős–Hajnal polynomial-to-exponential transition and settling all remaining $k=3$ cases.
desk verdict A landmark result if the computer check holds up: settles Erdős–Hajnal for k=3, with a genuinely new exact Turán theorem, but the decisive finite verification is not shipped with the paper. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the balanced iterated blowup of an edge: split the $n$ vertices into $k$ as-equal-as-possible parts, include every $k$-edge meeting each part exactly once, then recurse inside each part; $g_k(n)$ is the number of edges this construction produces. The proof's backbone is the reduction of the Turán statement to a coloring claim, Theorem 2.3: every $k$-partite edge-coloring of the complete graph $K_n$ has at most $g_k(n)$ monochromatic copies of $K_k$. For $k=3$, the proof is carried by the study of precyclic triangles — triangles whose edges are either two of one color and one of another with the imbalance in the wrong direction, or three distinct colors — together with an auxiliary function $F(A,B,C)$ that lower-bounds how many precyclic triangles a vertex must create. This function drives an induction that forces the dominant color class to contain a spanning complete tripartite subgraph. For $k\ge 7$, the same structural conclusion is obtained from the Loomis–Whitney inequality and convexity, with a single numerical check at $k=7$.
What would settle it
Exhibit a tripartite coloring of $K_n$ with more than $g_3(n)$ monochromatic triangles for any single $n$; this directly refutes Theorem 2.3, and with it the $k=3$ part of the argument. Alternatively, run the computer verification described in Appendix B and find an $n\le 699$ (with $n\notin\{13,14,16,17\}$) for which the required inequalities fail, or produce a counterexample to the hand estimates for $n\ge 700$.
Extended reading notes
Core claim
The central claim, on the paper's own terms, is that the Erdős–Hajnal transition is real and occurs exactly where conjectured: for $k=3$ and every fixed $s>3$, $r_3(s, g_3(s)+1; t)=2^{\Omega(t^{2/3})}$, while $r_3(s, g_3(s); t)=t^{O(1)}$ was already known; the same exponential-in-a-power conclusion holds for all $k\ge 7$. The engine is an exact Turán-type theorem: the maximum number of edges in an $n$-vertex $k$-graph with all $2$-tight components $k$-partite is $g_k(n)$ for $k=3$ and $k\ge 7$, and a balanced iterated blowup of an edge attains this maximum. The paper reduces the Ramsey statement to an equivalent-looking coloring claim, that any $k$-partite edge-coloring of $K_n$ has at most $g_k(n)$ monochromatic copies of $K_k$. For $k=3$, the previously solved cases are exactly the values of $n$ for which the defect $d(n)=T(n)-g_3(n)$ vanishes, namely powers of $3$ and sums or differences of two powers of $3$; the new proof removes that restriction and treats all $n$.
Load-bearing premise
The $k=3$ result rests on a finite verification: a computer program must confirm a specific list of inequalities for every size up to $699$, with the four exceptional sizes $13,14,16,17$ handled by hand, and the analytic estimates in Appendix B must hold for every larger size; if either part has a gap, the main theorem for $k=3$ is not proved.
Editorial extensions
If this is right
- For every fixed $s>3$, the Ramsey number $r_3(s, g_3(s)+1; t)$ grows at least as $2^{\Omega(t^{2/3})}$, confirming the Erdős–Hajnal transition at the conjectured threshold for $k=3$.
- Because $r_3(s, g_3(s); t)=t^{O(1)}$ was already known, the transition separates the polynomial and exponential regimes by exactly one red edge.
- The same exact Turán-type theorem yields $r_k(s, g_k(s)+1; t)=2^{\Omega(t^{2/k})}$ for all $s>k\ge 7$.
- The exact extremal result — maximum edges with all tight components $k$-partite equals $g_k(n)$ — holds for every $n$, for $k=3$ and for $k\ge 7$, not merely asymptotically.
- The proof shows that the earlier partial results for $k=3$ were precisely the cases with $d(n)=0$, unifying them as a special case of the general theorem.
Reading between the lines
- Editorial extension: the exponent $2/3$ is inherited from the borrowed coloring theorem of [6], not from the new Turán machinery; an improvement in that theorem's blue-clique bound would likely push the Ramsey exponent toward the paper's conjectured $2^{\Omega(t)}$.
- Editorial extension: the paper conjectures the same exact extremal statement for $k=4,5,6$; if that conjecture holds, the reduction used here would settle the polynomial-to-exponential transition for those uniformities as well.
- Editorial extension: the exactness of the balanced iterated blowup for all $n$ suggests a broader principle — that among hypergraphs whose tight components are restricted to a hereditary class, the recursive balanced construction maximizes edges — which could be tested for other tightness notions.
- Editorial extension: because the small-$n$ range is delegated to a computer program, formalizing or independently rechecking that program would either close the residual gap or expose a missing case.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves the Erdős–Hajnal conjecture for 3-uniform hypergraphs: for every fixed s>3, the Ramsey number r_3(s,g_3(s)+1;t) is exponential in t^{2/3}, while the polynomial side was known. The proof reduces the problem to a new exact Turán-type theorem (Theorem 1.5, equivalently Theorem 2.3 for k=3): any tripartite edge-coloring of K_n has at most g_3(n) monochromatic triangles, with the balanced iterated blowup of an edge extremal. The k=3 proof is a minimal-counterexample induction using degree-sequence bounds and a tournament/cyclic-triangle estimate, leaving a finite range n≤699 to a computer program and treating n≥700 by hand estimates. A separate convexity argument proves the same Turán-type statement for k≥7.
Significance. If the proof is correct, the paper settles the last open case of a central Erdős–Hajnal conjecture and introduces an exact hypergraph Turán problem whose extremizer is an iterated blowup. The reduction chain (Theorem 1.5 plus the external Theorem 2.2) is natural, and the degree-sequence lemmas in §2.2 are elegant and appear correct. The paper also gives credit to the prior work of Conlon–Fox–Sudakov and Mubayi–Razborov, and it does not rely on fitted constants or definitional equivalences. However, the k=3 proof is not fully self-contained: it depends on an unshipped computer verification, and a key small-n reduction (Lemma 3.3) is false as stated. The k≥7 argument also contains an invalid extremal bound.
major comments (3)
- [§3, Lemma 3.3] Lemma 3.3 is false as stated. The proof claims that if a vertex v has exactly one incident edge of each of two colors c1<c2, then recoloring the c2-edge by c1 preserves tripartiteness because v then has degree two in c1. This is not true. For example, let color c1 be a star centered at x with leaves v and y, and let the single edge vy have color c2. Before recoloring both color classes are tripartite, and v has exactly one c1-edge and one c2-edge. After recoloring vy to c1, the color-c1 graph contains the triangle xvy, so it is not tripartite. The proof of Proposition 3.4 explicitly invokes Lemma 3.3 ('take χ to be the coloring guaranteed by Assumption 3.1 and Lemma 3.3'), so the treatment of n=13,14,16,17 is unsupported. Since these are exactly the values excluded from the computer verification in Appendix B, the k=3 case of Theorem 2.3 is not established by the manuscript as written.
- [§4 and Appendix B.1] The decisive finite verification for all n≤699 outside {13,14,16,17} is delegated to a computer program that is not shipped with the paper. The final paragraph of §4 states that all the required checks—the hypotheses of Lemmas 4.7, 4.13, and 4.15 and the inequality τ≤2min(|X*|,|Y*|,|U|)—are verified in Appendix B, but the actual verification for n≤699 is only described at a high level and the code is available only at an external URL with no version, commit hash, or certificates. In addition, Lemma B.5 begins with a computer check of d(n)≤0.05891 n log n for 200≤n<600 that is also not reproduced. Consequently the central claim of the paper is not testable from the submission. The authors should provide the code as ancillary material, together with deterministic outputs or certificates sufficient for an independent auditor to reproduce the finite checks.
- [§5, proof of Lemma 5.2] The bound on A in the proof of Lemma 5.2 is invalid. The text asserts, via the Loomis-Whitney inequality, that the number of monochromatic copies of K_{k-2} in colors other than c* is at most (α C(n,2)/C(k-2,2))^{(k-2)/2}. This inequality is not a consequence of Loomis-Whitney and is false already for a single k-partite color class: take the complete 7-partite graph with one vertex in each part. It has e=21 edges and C(7,5)=21 copies of K_5, while (21/C(5,2))^{5/2}≈6.4. Thus the displayed bound on A, and with it the conclusion A<B in Lemma 5.2, are unsupported. The k≥7 part of Theorem 2.3 therefore needs a correct extremal estimate (for example via Newton's inequalities), after which the numerical verification of condition (16) must be redone; note that the numerical check at k=7,n=43 is also given only to four decimal places and is not a rigorous interval-arithmetic proof.
minor comments (3)
- [Figure 1] The caption 'Figure 1: Schematic of the parts described by Definition 4.4' appears in the text, but the figure itself is not included in the manuscript; please either include the figure or remove the caption.
- [Appendix B.2, Lemma B.5] The bound d(n)≤0.05891 n log n for 200≤n<600 is said to be checked by 'Section 3 of the program'; this should be made self-contained or the check should be included in the ancillary material, since it is the base of the induction for all n≥700.
- [§5, numerical verification] The verification for k=7,n=43 in §5 reports α, β, γ to four decimal places and notes that the final inequality holds with a margin of about 4×10^{-4}; this needs a rigorous interval-arithmetic or exact rational proof, especially because the inequality is strict.
Circularity Check
The new Turán theorem is self-contained, but the headline exponential lower bound is imported as a load-bearing self-citation from [6], a preprint co-authored by two of the present authors.
-
self citation load bearing
[Section 2.1, Theorem 2.2 and the proof of Theorem 1.3; k≥7 remark]
"To obtain Theorem 1.3 from Theorem 1.5, we use the main theorem from [6]. Theorem 2.2 ([6, Theorem 2.1]). For every k ≥ 3 and positive integer N , there is a red/blue edge coloring of K (k) N such that any red 2-tightly connected subgraph is k-partite and the largest blue clique has size O((log N )k/2). ... Theorem 2.2 implies that M ≥ 2Ω(t2/k)."
The exponential lower bound in the paper's main theorem is not derived from the paper's own theorems. The proof of Theorem 1.3 says 'Theorem 2.2 implies that M ≥ 2^{Ω(t^{2/k})}', where Theorem 2.2 is quoted from [6, Theorem 2.1], a preprint co-authored by He and Yu, two of the three present authors. The manuscript does not re-prove or independently certify that theorem, and for k≥7 it extends it by remark ('the same proof goes through for all higher uniformities'). Thus the entire exponential side of the headline claim rests on a load-bearing self-citation: if [6, Theorem 2.1] were unavailable, Theorem 1.5 alone would not yield Theorem 1.3. This is not a fitted-input or definitional circle, but it is a genuine self-citation chain at the central step.
full rationale
The paper's central new contribution, Theorem 1.5 / Theorem 2.3, is proved by an internal induction: Section 3 handles n = 13, 14, 16, 17 by hand; Section 4 reduces all other n to the starred lemmas and the final bound τ ≤ 2 min(|X*|, |Y*|, |U|); Section 5 gives a self-contained proof for k ≥ 7. I found no fitted parameter renamed as a prediction and no quantity whose definition already contains the claimed conclusion: g3(n) is defined by the iterated-blowup recurrence independently of the extremal theorem, and Theorem 1.5 is a genuine upper bound with a matching construction. The only circularity-like link is the use of Theorem 2.2 from [6] to obtain the exponential lower bound in Theorem 1.3: [6] is a preprint by the second and third authors and collaborators, the theorem is quoted rather than proved, and without it the paper's Theorem 1.5 alone yields at most the polynomial side. This is load-bearing self-citation, so the score is 4 rather than 0. The computer verification in Appendix B is a verification/reproducibility gap rather than circularity: it checks explicit finite inequalities for n ≤ 699 and the hand estimates for n ≥ 700 use those values recursively, but the code is linked rather than shipped, so the decisive finite check cannot be audited from the submission. That gap lowers confidence in correctness but does not make the derivation self-referential. Overall, there is no definitional or fitted circularity; the central claim retains substantial independent content, and the score reflects the unproved self-cited lower-bound theorem.
Assumptions & free parameters
free parameters (3)
- k=7 numerical constants (alpha, beta, gamma) at n=43 =
alpha ~ 0.2249, beta ~ 0.102, gamma ~ 0.3648
- Bound constant c_0 for d(n) <= c_0 n log n =
0.05891 (program range), 0.06 (Lemma B.5)
- Large-n thresholds: n >= 700, eta = 1/8, 0.45|U| cap =
700, 0.125, 0.45
assumptions (5)
- domain assumption Theorem 2.2 (from [6, Theorem 2.1]): for every k >= 3 and N there is a coloring of K_N^(k) with all red 2-tight components k-partite and largest blue clique O((log N)^{k/2}), including the k >= 4 extension noted in [6]'s conclusion.
- domain assumption The external computer program correctly verifies the assumptions of Lemmas 4.7, 4.13, 4.15 and tau <= 2min(...) for all n <= 699 outside {13, 14, 16, 17}.
- standard math g_k(n) is maximized by the balanced composition of n into k parts (proven in [15]).
- standard math Loomis-Whitney inequality and the k-partite clique bound t_i <= (e_i / C(k,2))^{k/2}.
- ad hoc to paper The numerically solved constants for k = 7, n = 43 satisfy the condition (16) of Lemma 5.2.
Cite this review
Pith. "Pith review of Polynomial-to-exponential transition in 3-uniform Ramsey numbers." pith.science (2026). https://pith.science/paper/JHBLZ4A2
@misc{pith2026250709434,
author = {Pith},
title = {Pith review of: Polynomial-to-exponential transition in 3-uniform Ramsey numbers},
year = {2026},
howpublished = {\url{https://pith.science/paper/JHBLZ4A2}},
note = {Machine review of arXiv:2507.09434}
}
abstract
Let $r_k(s, e; t)$ denote the smallest $N$ such that any red/blue edge coloring of the complete $k$-uniform hypergraph on $N$ vertices contains either $e$ red edges among some $s$ vertices, or a blue clique of size $t$. Erd\H os and Hajnal introduced the study of this Ramsey number in 1972 and conjectured that for fixed $s>k\geq 3$, there is a well defined value $h_k(s)$ such that $r_k(s, h_k(s)-1; t)$ is polynomial in $t$, while $r_k(s, h_k(s); t)$ is exponential in a power of $t$. Erd\H os later offered \$500 for a proof. Conlon, Fox, and Sudakov proved the conjecture for $k=3$ and $3$-adically special values of $s$, and Mubayi and Razborov proved it for $s > k \geq 4$. We prove the conjecture for $k=3$ and all $s$, settling all remaining cases of the problem. We do this by solving a novel Tur\'an-type problem: what is the maximum number of edges in an $n$-vertex $3$-uniform hypergraph in which all tight components are tripartite? We show that the balanced iterated blowup of an edge is an exact extremizer for this problem for all $n$.
Figures
Reference graph
Works this paper leans on
- [6]
-
[1]
N. Alon and J. Spencer, The Probabilistic Method , Fourth edition, Wiley Series in Discrete Math- ematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016
work page 2016
-
[2]
J. Balogh and H. Luo, Tur´ an Density of Long Tight Cycle Minus One Hyperedge, Combinatorica 44 (2024), 949–976
work page 2024
-
[3]
L. Bodn´ ar, J. L´ eon, X. Liu, and O. Pikhurko, The Tur´ an density of short tight cycles (2025), preprint available at arXiv:2506.03223 [math.CO]
arXiv 2025
- [4]
- [5]
- [7]
- [8]
Show all 18 references
-
[9]
Chung, Open problems of Paul Erd˝ os in graph theory, J
F. Chung, Open problems of Paul Erd˝ os in graph theory, J. Graph Theory 25 (1997), 3–36
1997
-
[10]
Erd˝ os, Problems and results on graphs and hypergraphs: similarities and differences, Mathematics of Ramsey Theory , Algorithms Combin., 5, 12–28, Springer, Berlin, 1990
P. Erd˝ os, Problems and results on graphs and hypergraphs: similarities and differences, Mathematics of Ramsey Theory , Algorithms Combin., 5, 12–28, Springer, Berlin, 1990
1990
-
[11]
Erd˝ os and A
P. Erd˝ os and A. Hajnal, On Ramsey like theorems, Problems and results, in Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), 123–140, Inst. Math. Appl., Southend-on-Sea, 1972
1972
-
[12]
Kamˇ cev, S
N. Kamˇ cev, S. Letzter, and A. Pokrovskiy, The Tur´ an density of tight cycles in three-uniform hyper- graphs, Int. Math. Res. Not. 2024 (2023), 4804-4841
2023
-
[13]
Lidick´ y, C
B. Lidick´ y, C. Mattes, and F. Pfender, The hypergraph Tur´ an densities of tight cycles minus an edge (2024), preprint available at arXiv:2409.14257 [math.CO]
2024 arXiv
-
[14]
Mattheus and J
S. Mattheus and J. Verstra¨ ete, The asymptotics of r(4, t), Annals Math. 199 (2024), 919–941
2024
-
[15]
Mubayi and A
D. Mubayi and A. Razborov, Polynomial to exponential transition in Ramsey theory, Proc. London Math. Soc. 122 (2021), 69–92
2021
-
[16]
Mubayi and A
D. Mubayi and A. Suk, The Erd˝ os-Hajnal hypergraph Ramsey problem, J. Eur. Math. Soc. 22 (2020), 1247–1259. 27 Appendix A Proof of Lemma 4.9 In this section, we prove the following about the function F from Definition 4.8. Lemma 4.9. The following are true. (a) The infimum in...
2020
-
[17]
The bmax from Lemma B.3 is at most |U |/2
-
[18]
Then for every x ∈ X ∗, bU (x) ≤ $ P 2 − (bXY − |Y ∗|)+ + bU,Y ∗ |Y ∗| %
We have the inequality F |Y ∗|, |U | − P − 2(bXY − |Y ∗|)+ + 2bU,Y ∗ 2|Y ∗| , |X ∗| + |Y ∗| + ∆ 2 > P− 2(bXY − |Y ∗|)+ + bU,Y ∗ . Then for every x ∈ X ∗, bU (x) ≤ $ P 2 − (bXY − |Y ∗|)+ + bU,Y ∗ |Y ∗| % . Proof. Let us first show that either criterion implies bU (x) ≤ |U |/2 f...
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.