REVIEW 1 major objections 4 minor 18 references
Ramsey games near the critical threshold
T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper proves that near the H-Ramsey threshold, every H-free colouring of a random graph is destroyed by ω(1) extra random edges, for any H with an edge whose removal lowers its 2-density.
desk verdict Solid generalization of the FKRRRT Ramsey-games result, but the proof as written leaves out the m2(H)=1 case (e.g., P4) because Lemma 3.9 relies on Proposition 3.5, which only covers m2(H)>1. 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 load-bearing object is the reduced k-fold edge-rooted product G⊙k(H,h): take a central copy of G, attach k copies of H to each edge of G along the root edge h, and delete the central edges. Lemma 2.3(c) states that if m2(H\h)<m2(H), then m2(H⊙2(H,h))<m2(H). This strict density drop is what allows the sparse counting lemma to find many copies of H⊙2(H,h) inside G(n,p) when p is a constant times $n^{{-1/m2(H)}}$. In each such copy the central H has every edge simultaneously supported by a red and a blue copy of H−h, making the whole central copy colour-forced. A sparse regularity lemma for upper-uniform graphs supplies the reduced graph in which Corollary 3.10 finds a vertex lying in two monochromatic cliques, and the counting lemma converts those cliques into the required forced copies.
What would settle it
Choose any graph H satisfying the edge-deletion condition, set p=c $n^{{-1/m2(H)}}$ and q=$n^{{-2}}$\log n. The theorem asserts that with probability tending to 1, every H-free 2-colouring of G(n,p) fails to extend to G(n,p)∪G(n,q) after any colouring of the added edges. If for infinitely many n one can exhibit an H-free colouring of G(n,p) and a colouring of the added edges that keeps the union H-free, with probability bounded below, then conclusion (a) of Theorem 1.1 is false.
Extended reading notes
Core claim
The central discovery is that, near the H-Ramsey threshold, every H-free colouring of the random graph is saturated with colour-forced structures. Given a 2-colouring of G(n,p) with p=c $n^{{-1/m2(H)}}$ and no monochromatic copy of H, the graph contains Ω($n^{2}$) pairs of vertices that are simultaneously bases of a red copy of H−h and a blue copy of H−h; such a pair is green-forced, because colouring the new edge either colour completes a monochromatic H. Hence if any one of these pairs is hit by an extra random edge, no H-free extension is possible. For 3-colourings the same forcing construction produces Ω($n^{{v(H)}}$) χ-forced copies of H for some colour χ, so the second random graph only needs to contain one such copy, which it does once q3=ω($n^{{-1/m(H)}}$). The proof works by finding two monochromatic cliques in the reduced graph of a sparse regular partition and then using a counting lemma on the reduced edge-rooted product H⊙2(H,h), whose 2-density is strictly below m2(H).
Load-bearing premise
The argument hinges on H having an edge h whose removal strictly lowers the graph's 2-density; if no single edge has that effect, the density gap that drives the counting step disappears.
Editorial extensions
If this is right
- For every strictly 2-balanced H, at p=c n^{-1/m2(H)} the random graph is already essentially Ramsey for 2 colours: any H-free colouring is destroyed by ω(1) extra random edges.
- The two-colour added-edge density is optimal: if q2=O(n^{-2}), then with positive probability the extra graph has no edges and the colouring extends, so ω(n^{-2}) is the smallest rate that can force a monochromatic H.
- The three-colour added-edge density, ω(n^{-1/m(H)}), is also optimal up to a constant factor: if q3=O(n^{-1/m(H)}), then with positive probability the extra graph is itself H-free and can be coloured in the third colour.
- The result cannot be extended to four or more colours at these densities, because the two random graphs can be coloured with disjoint pairs of colours, avoiding a monochromatic H until one graph reaches the ordinary random Ramsey threshold.
- Some condition on H is genuinely necessary: there are 2-balanced graphs, built from edge-rooted products, for which the conclusion of Theorem 1.1 fails, and the paper's hypothesis is sufficient but not necessary.
Reading between the lines
- Inference: the proof can be read as showing that every H-free 2-colouring of G(n,p) has Ω(n^2) uncolourable pairs, so the random graph at the threshold is only one carefully placed edge away from being Ramsey; quantifying this set for a given H could give a sharper measure of Ramsey-criticality.
- Inference: the three-colour exponent 1/m(H) suggests a general hierarchy: with more colours, the second round may need the added graph to contain an entire forced copy of H rather than a single forced edge, and the r≥4 obstruction shows this hierarchy must break once the two rounds can be coloured independently.
- Inference: the conditions of Theorem 4.1—two sparse graphs Fred and Fblue straddling a matching M, with H appearing after any 2-colouring of M—hint at a route to a full classification of graphs for which the near-threshold extension statement holds; testing whether all such graphs admit such a forcing pair would settle the open problem.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a two-round Ramsey game on the binomial random graph. Its main result (Theorem 1.1) asserts that if H has an edge h whose deletion lowers m_2, then for p=c n^{-1/m_2(H)} the graph G=G_{n,p} a.a.s. has the property that every monochromatic-H-free 2-edge-colouring is unextendable to G union G_{n,q2} for q2=omega(n^{-2}), and every monochromatic-H-free 3-edge-colouring is unextendable to G union G_{n,q3} for q3=omega(n^{-1/m(H)}). The proof combines a sparse regularity partition of G, a reduced-graph argument producing a vertex in two monochromatic cliques of distinct colours, and the sparse counting lemma to produce many colour-forced copies of H. The paper also proves a necessity result (Theorem 2.4) using edge-rooted products and gives a more general sufficient condition (Theorem 4.1) showing that the m_2-decreasing-edge condition is not necessary.
Significance. The main theorem, if its proof is completed, is a substantial and natural generalization of the Friedgut-Kohayakawa-Rodl-Rucinski-Tetali triangle result to all graphs with an edge whose deletion lowers the 2-density, answering a question raised in that earlier paper. The proof is carefully organized around established tools (sparse regularity, sparse counting, random graph concentration), and it identifies a clean structural condition. The paper is also honest about limitations: Theorem 2.4 shows some condition is necessary, and Theorem 4.1 shows the particular condition is not optimal. The main weakness is a gap for forests with m_2(H)=1, noted below.
major comments (1)
- [Section 3.3 (Lemma 3.9); Proposition 3.5] The proof of Lemma 3.9 begins by applying Proposition 3.5 to assert that G[W] contains many edge-disjoint copies of H, but Proposition 3.5 is stated only for graphs with m_2(H)>1. Theorem 1.1 does not imply this restriction: for H=P4 and h the middle edge, m_2(P4)=1 and m_2(P4-h)=1/2, so the hypothesis of Theorem 1.1 holds while Proposition 3.5 does not apply. The constants kappa(H) and the function f(rho) in Lemma 3.9 are therefore not defined for this class of graphs, and Proposition 3.11, which depends on Lemma 3.9, has no starting point. This case is not vacuous: for p=c/n and sufficiently small c, G_{n,p} has linearly many copies of P4 and, by a standard Lovasz Local Lemma argument, admits 2-colourings with no monochromatic P4. The result may still be true and the gap appears repairable, but the proof as written does not cover all H allowed by the statement.
minor comments (4)
- [Section 3.3, Lemma 3.9] The phrase 'each appear on at least 12 rho f(rho) n^2 p edges of G[W]' should refer to edge-disjoint copies in which the colour appears, not to edges; a copy can contain several edges, and the subsequent counting uses the number of copies.
- [Section 3.4, Corollary 3.10] The condition 6 rho_{2t-3} f(rho_{2t-3}) >= 3 epsilon + alpha/2 is not explicitly verified from the parameter choices; it follows because 6 rho f(rho) = rho^{2-v(H)}/(4 kappa c^{e(H)-1}) and v(H)>=3 imply the left side only grows as rho decreases, so this should be spelled out.
- [Section 4, Theorem 4.1] Theorem 4.1 is stated as flowing from the proof of Theorem 1.1(a), but no formal proof is provided; if it is to be cited as a result, a proof sketch should be included.
- [References and typography] The text contains several typos, such as '/suppress Luczak' in References [9] and [4], and inconsistent spacing in expressions such as 'm2(H \h)<m 2(H)' throughout; these should be corrected.
Circularity Check
No significant circularity; the derivation is self-contained given its explicit structural hypothesis and independent cited theorems.
full rationale
The paper's central claim, Theorem 1.1, is proved by constructing colour-forced copies of H in the first random graph via the reduced graph of a sparse regular partition. The key structural step, Lemma 2.3(c), is proved directly from the definition of 2-density and the hypothesis that there is an edge h with m2(H\h)<m2(H); it is not assumed as an input. The counting and regularity tools used (Proposition 3.5, Theorems 3.7 and 3.8) are cited from published external or multi-author sources with full proofs, including the sparse counting lemma of Conlon, Gowers, Samotij and Schacht; although one present author is among the contributors to that lemma, the lemma is an established, peer-reviewed result proved independently of the present problem, and the paper does not rely on any unproved or tailored form of it. The q2 and q3 thresholds are matched by simple, explicitly argued lower-bound constructions (no edges with positive probability, or colouring the extra graph with an unused colour, or H-free extra graphs), so the claimed sharpness is not derived from the same mechanism that produces the forcings. The proof does feed the hypothesis m2(H\h)<m2(H) into Lemma 2.3(c) to force the density drop m2(H⊙2(H,h))<m2(H), but this is the stated sufficient condition and is used transparently rather than smuggled in by definition or by a self-citation chain. The reviewer-level concern that Proposition 3.5 is stated only for m2(H)>1 while Theorem 1.1 also allows forests with m2(H)=1 is a possible correctness gap for a class of H allowed by the statement, not a circularity: it does not make any prediction equal to an input or make the conclusion follow from its own assumptions by construction. Accordingly, no circular step satisfies the required evidentiary standard of exhibiting a specific reduction of the claimed result to its inputs.
Assumptions & free parameters
assumptions (5)
- standard math Sparse regularity lemma (Kohayakawa-Rödl, Theorem 3.7)
- standard math Sparse counting lemma (Conlon-Gowers-Samotij-Schacht, Theorem 3.8)
- standard math Rödl-Ruciński random Ramsey theorem
- standard math Proposition 3.5 (many edge-disjoint copies of H in induced subgraphs of G_{n,p})
- standard math Probability concentration bounds (Hoeffding, Chebyshev, Markov)
Cite this review
Pith. "Pith review of Ramsey games near the critical threshold." pith.science (2026). https://pith.science/paper/VBZY4SQZ
@misc{pith2026190802991,
author = {Pith},
title = {Pith review of: Ramsey games near the critical threshold},
year = {2026},
howpublished = {\url{https://pith.science/paper/VBZY4SQZ}},
note = {Machine review of arXiv:1908.02991}
}
abstract
A well-known result of R\"odl and Ruci\'nski states that for any graph $H$ there exists a constant $C$ such that if $p \geq C n^{- 1/m_2(H)}$, then the random graph $G_{n,p}$ is a.a.s. $H$-Ramsey, that is, any $2$-colouring of its edges contains a monochromatic copy of $H$. Aside from a few simple exceptions, the corresponding $0$-statement also holds, that is, there exists $c>0$ such that whenever $p\leq cn^{-1/m_2(H)}$ the random graph $G_{n,p}$ is a.a.s. not $H$-Ramsey. We show that near this threshold, even when $G_{n,p}$ is not $H$-Ramsey, it is often extremely close to being $H$-Ramsey. More precisely, we prove that for any constant $c > 0$ and any strictly $2$-balanced graph $H$, if $p \geq c n^{-1/m_2(H)}$, then the random graph $G_{n,p}$ a.a.s. has the property that every $2$-edge-colouring without monochromatic copies of $H$ cannot be extended to an $H$-free colouring after $\omega(1)$ extra random edges are added. This generalises a result by Friedgut, Kohayakawa, R\"odl, Ruci\'nski and Tetali, who in 2002 proved the same statement for triangles, and addresses a question raised by those authors. We also extend a result of theirs on the three-colour case and show that these theorems need not hold when $H$ is not strictly $2$-balanced.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
N. Alon and J. Spencer, The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New Je rsey, 2008
work page 2008
- [2]
-
[3]
D. Conlon and W. T. Gowers, Combinatorial theorems in spa rse random sets, Ann. of Math. 184 (2016), 367–454. 17
work page 2016
- [4]
- [5]
-
[6]
E. Friedgut, Y. Kohayakawa, V. R¨ odl, A. Ruci´ nski and P. Tetali, Ramsey games against a one-armed bandit, Combin. Probab. Comput. 12 (2003), 515–545
work page 2003
-
[7]
S. Gerke and A. Steger, The sparse regularity lemma and it s applications, in Surveys in com- binatorics 2005, 227–258, London Math. Soc. Lecture Note Se r., 327, Cambridge Univ. Press, Cambridge, 2005
work page 2005
-
[8]
L. Gugelmann, R. Nenadov, Y. Person, N. ˇSkori´ c, A. Steger and H. Thomas, Symmetric and asymmetric Ramsey properties in random hypergraphs, Forum Math. Sigma 5 (2017), e28, 47 pp
work page 2017
Show all 18 references
-
[9]
Janson, T
S. Janson, T. /suppress Luczak and A. Ruci´ nski,Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New Yo rk, 2000
2000
-
[10]
Kohayakawa, Szemer´ edi’s regularity lemma for sparse graphs, in Foundations of computa- tional mathematics (Rio de Janeiro, 1997), 216–230, Spring er, Berlin, 1997
Y. Kohayakawa, Szemer´ edi’s regularity lemma for sparse graphs, in Foundations of computa- tional mathematics (Rio de Janeiro, 1997), 216–230, Spring er, Berlin, 1997
1997
-
[11]
Mousset, R
F. Mousset, R. Nenadov and W. Samotij, Towards the Kohay akawa–Kreuter conjecture on asymmetric Ramsey properties, Combin. Probab. Comput. , to appear
-
[12]
Nenadov and A
R. Nenadov and A. Steger, A short proof of the random Rams ey theorem, Combin. Probab. Comput. 25 (2016), 130–144
2016
-
[13]
Powierski, Ramsey properties of randomly perturbed dense graphs, preprint available at arXiv:1902.02197 [math.CO]
E. Powierski, Ramsey properties of randomly perturbed dense graphs, preprint available at arXiv:1902.02197 [math.CO]
1902 arXiv
-
[14]
R¨ odl and A
V. R¨ odl and A. Ruci´ nski, Lower bounds on probability thresholds for Ramsey properties, in Combinatorics, Paul Erd˝ os is eighty, Vol. 1, 317–346, Boly ai Soc. Math. Stud., J´ anos Bolyai Math. Soc., Budapest, 1993
1993
-
[15]
R¨ odl and A
V. R¨ odl and A. Ruci´ nski, Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), 917–942
1995
-
[16]
Saxton and A
D. Saxton and A. Thomason, Hypergraph containers, Invent. Math. 201 (2015), 925–992
2015
-
[17]
Schacht, Extremal results for random discrete struc tures, Ann
M. Schacht, Extremal results for random discrete struc tures, Ann. of Math. 184 (2016), 333– 365
2016
-
[18]
Schacht and F
M. Schacht and F. Schulenburg, Sharp thresholds for Ram sey properties of strictly balanced nearly bipartite graphs, Random Structures Algorithms 52 (2018), 3–40. 18
2018
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.