{"id":"f8f6cf4d-7332-424b-8152-e78a9d0f3d81","arxiv_id":"1908.02991","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every graph H with an edge whose deletion lowers its 2-density, G(n, c n^-1/m2(H)) is a.a.s. such that every H-free 2-coloring is destroyed by adding omega(1) random edges; a similar 3-colour statement holds.","lead":"This paper proves that random graphs just below the Ramsey threshold are already extremely close to being Ramsey: any coloring of the first graph without a monochromatic copy of H becomes impossible to extend after just a handful of extra random edges. It generalizes a 2003 triangle result to all graphs satisfying a mild density condition, and shows the condition cannot be dropped entirely.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.1 includes m2(H)=1 forests (e.g., P4), but Lemma 3.9 invokes Prop 3.5, which is stated only for m2(H)>1; no alternative argument is supplied.","rationale":"The reader’s weakest assumption was the structural condition m2(H\\h)<m2(H) and the density gap in Lemma 2.3(c). I do not think that is the most load-bearing point: Lemma 2.3(c) is carefully argued and the condition is clearly sufficient for the counting step. The genuine soft spot is a mismatch between the theorem’s scope and the cited tool. Proposition 3.5, which supplies the edge-disjoint copies of H used throughout Lemma 3.9, is stated only for m2(H)>1. The theorem’s hypothesis allows m2(H)=1, and there are non-vacuous examples such as P4. This is not a manufactured objection: the proof literally uses Proposition 3.5 for an arbitrary H satisfying the theorem, and no substitute is offered for forests. The gap is likely fixable, since the analogue of Proposition 3.5 for trees should follow from a simple greedy packing, but it is absent from the manuscript. Because the central claim is unsupported for a non-empty class of H as written, I would not accept without a revision that either proves the m2=1 analogue or restricts the theorem accordingly. I therefore recommend CONDITIONAL rather than UNCHANGED or REJECT: the main ideas are sound, and the missing case appears repairable, but the submitted proof does not yet cover its own statement.","tokens_in":17627,"tokens_out":63265,"duration_ms":692926,"concrete_test":"For a fixed tree H with e(H)≥2 and p=c/n, prove or disprove that with high probability every induced subgraph of G_{n,p} on at least ρn/2 vertices contains Ω(c^{e(H)} n) edge-disjoint copies of H. A greedy packing argument using that each edge lies in O(1) copies should work. If the statement holds, insert it as a companion to Proposition 3.5 and Lemma 3.9 covers the m2=1 cases. If it fails, run a small-n exhaustive check for H=P4: compute, over all P4-free 2-colourings of G_{n,c/n}, the minimum number of pairs that are both red- and blue-bases; a subquadratic count would refute Theorem 1.1(a) for this class.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Proposition 3.11 is driven by Lemma 3.9, whose proof begins: “By Proposition 3.5, we may assume G[W] contains at least 24ρf(ρ)n^2p edge-disjoint copies of H.” However, Proposition 3.5 is explicitly restricted to graphs with m2(H)>1. The hypothesis of Theorem 1.1 does not imply this: H=P4 with h the middle edge has m2(P4)=1 and m2(P4\\h)=1/2, so it satisfies the theorem’s condition. For p=c/n, G_{n,p} contains linearly many P4 copies, and for sufficiently small c there exist 2-colourings with no monochromatic P4 (by a Lovász Local Lemma argument), so this case is not vacuous. The constants κ and the function f(ρ) in Lemma 3.9 come from Proposition 3.5, so their existence is unproved for exactly this class of forests. Without edge-disjoint copies of H, the density argument on the reduced graph has no starting point. The theorem may still be true, and the gap may be repairable, but the proof as written does not cover all H allowed by the statement.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17863,"tokens_out":9009,"duration_ms":90696,"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":[{"comment":"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.","section":"Section 3.3 (Lemma 3.9); Proposition 3.5"}],"minor_comments":[{"comment":"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":"Section 3.3, Lemma 3.9"},{"comment":"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":"Section 3.4, Corollary 3.10"},{"comment":"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.","section":"Section 4, Theorem 4.1"},{"comment":"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.","section":"References and typography"}],"recommendation":"major_revision","confidential_remarks":"The only load-bearing issue is the m_2(H)=1 gap. It appears local and likely repairable, either by extending Proposition 3.5 to forests or by treating forests separately, so I would not reject the paper on this basis. The manuscript's use of sparse regularity and sparse counting results, several co-authored by one of the present authors, is appropriate because those are established published theorems with full proofs. No concerns about novelty disclosure."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this is a real advance on the Friedgut–Kohayakawa–Rödl–Ruciński–Tetali result, and the main theorem is likely true, but the proof as written doesn't cover every H allowed by the statement. The gap is in the m2(H)=1 regime, e.g., P4. Lemma 3.9 starts by invoking Proposition 3.5 to get many edge-disjoint copies of H inside a large induced subgraph of G_{n,p}, and Proposition 3.5 is stated only for m2(H)>1. The theorem's hypothesis doesn't exclude m2(H)=1: P4 with the middle edge removed has m2=1/2 < 1 = m2(P4). So the current proof leaves out exactly the forests that satisfy the condition. This looks repairable — a version of Proposition 3.5 for trees should hold with the same kind of bound, perhaps with a separate argument — but it's not in the paper.\n\nWhat's good: the paper answers an explicit open question from FKRRRT, extends the triangle result to a broad class of H, gives a clean description of the role of the density condition via edge-rooted products, and proves that some condition is necessary. The counterexamples in Section 2 are a nice addition, and Theorem 4.1 shows the condition isn't best possible. The proof strategy is sound overall: the reduced graph argument, Lemma 2.3(c) for the density drop, and the sparse counting lemma fit together. The overcounting step in Section 3.4 is intricate, but I didn't find an error there.\n\nOther than the m2=1 gap, the softer issues are minor: a few typos (including a stray 'suppress' in the references), and the paper is dense reading. The citations to Conlon–Gowers–Samotij–Schacht are to the right tool and not a concern.\n\nWho should read it: people working in random Ramsey theory and threshold phenomena. It deserves a serious referee, but the referee should demand the m2=1 case be fixed or the statement adjusted.\n\nRecommendation: send it to peer review; expect major revision.","headline":"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.","tokens_in":18402,"tokens_out":4822,"would_cite":true,"duration_ms":45641,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05D10","05C55"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["random graphs","Ramsey theory","Ramsey games","thresholds","2-density","sparse regularity","edge-rooted products","strictly 2-balanced graphs"],"falsifier":"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.","tokens_in":17441,"feed_emoji":"🎲","tokens_out":11543,"duration_ms":117300,"temperature":0.7,"pith_summary":"At the threshold where a random graph is about to become Ramsey for a fixed graph H, the paper shows the graph is already almost Ramsey in a strong sense. For any H that has an edge whose deletion strictly lowers its 2-density (a standard subgraph-density measure underlying the Ramsey threshold), and for p=c $n^{{-1/m2(H)}}$, the random graph G(n,p) has the following property with high probability: every 2-colouring of its edges with no monochromatic H is frozen, because adding ω(1) random extra edges, coloured in any way, forces a monochromatic H. The analogous statement for 3-colourings holds when the added-random-graph density is ω($n^{{-1/m(H)}}$). This generalises a 2002 result for triangles and answers the question that result raised, while also showing that some condition on H is necessary: there are graphs for which the conclusion fails.","feed_headline":"Near the Ramsey threshold, no H-free colouring survives ω(1) new edges","feed_subtitle":"Any graph with an edge that lowers its 2-density is already almost Ramsey in the random graph.","key_machinery":"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.","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes the threshold theorem for H-Ramsey properties of G(n,p), fixing n^{-1/m2(H)} as the reference point for the near-threshold setting.","marker":"[15]"},{"why":"Proves the triangle case of the two- and three-colour extension statements, which this paper generalises and whose question it answers.","marker":"[6]"},{"why":"Provides the sparse counting lemma used to produce many copies of H⊙2(H,h) inside G(n,p), the step that yields colour-forced copies of H.","marker":"[4]"},{"why":"Supplies the sparse regularity lemma for upper-uniform graphs used to build the reduced graph and find two monochromatic cliques.","marker":"[10]"},{"why":"Supplies the concentration result for edge-disjoint copies of H in G(n,p), needed in the reduced-graph argument to find pairs of colours.","marker":"[9]"},{"why":"Provides the block argument controlling 2-density in subgraphs, used in the edge-rooted product computations.","marker":"[12]"},{"why":"Supplies the concentration result guaranteeing that one of the many colour-forced copies of H appears in the added random graph G(n,q3).","marker":"[1]"}],"fun_headline_variants":["Near Ramsey threshold, H-free colorings die fast","Almost Ramsey: random graphs saturated near critical p","Edge-saturation: random graphs are barely non-Ramsey","Near threshold, every H-free coloring is one edge from failure","Saturated colorings: random graphs are almost Ramsey"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Near Ramsey threshold, H-free colorings die fast","Almost Ramsey: random graphs saturated near critical p","Edge-saturation: random graphs are barely non-Ramsey","Near threshold, every H-free coloring is one edge from failure","Saturated colorings: random graphs are almost Ramsey"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000625,"raw_usage":{"total_tokens":2978,"prompt_tokens":1118,"completion_tokens":1860,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":734,"completion_tokens_details":{"reasoning_tokens":1781}},"tokens_in":734,"tokens_out":1860,"duration_ms":16118,"temperature":1.0,"reasoning_tokens":1781,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:31:34.895484+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"R¨ odl and A","cited_arxiv_id":null,"evidence_quote":"Establishes the threshold theorem for H-Ramsey properties of G(n,p), fixing n^{-1/m2(H)} as the reference point for the near-threshold setting."},{"cited_title":"Friedgut, Y","cited_arxiv_id":null,"evidence_quote":"Proves the triangle case of the two- and three-colour extension statements, which this paper generalises and whose question it answers."},{"cited_title":"Conlon, W","cited_arxiv_id":null,"evidence_quote":"Provides the sparse counting lemma used to produce many copies of H⊙2(H,h) inside G(n,p), the step that yields colour-forced copies of H."},{"cited_title":"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","cited_arxiv_id":null,"evidence_quote":"Supplies the sparse regularity lemma for upper-uniform graphs used to build the reduced graph and find two monochromatic cliques."},{"cited_title":"Janson, T","cited_arxiv_id":null,"evidence_quote":"Supplies the concentration result for edge-disjoint copies of H in G(n,p), needed in the reduced-graph argument to find pairs of colours."},{"cited_title":"Nenadov and A","cited_arxiv_id":null,"evidence_quote":"Provides the block argument controlling 2-density in subgraphs, used in the edge-rooted product computations."},{"cited_title":"Alon and J","cited_arxiv_id":null,"evidence_quote":"Supplies the concentration result guaranteeing that one of the many colour-forced copies of H appears in the added random graph G(n,q3)."}],"review_version":1}