{"id":"45044bda-5770-4956-b51d-ce152fc0e231","arxiv_id":"2508.03835","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A general framework of chain constructions yields quadratic or almost quadratic lower bounds on the maximum running time of H-bootstrap percolation for dense graphs, random graphs, wheels, and bipartite graphs.","lead":"This paper studies how long a graph process can run before stopping, where new edges appear when they complete a copy of a fixed graph H. It introduces a general construction method showing that for many graphs H, including almost all random graphs, the process can last a quadratic number of steps, the theoretical maximum.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The quadratic and random-graph results appear robust; the load-bearing risk is Theorem 7.3's new Ruzsa-type set construction, on which Theorems 7.13/1.8 rest.","rationale":"I read the full manuscript and paid particular attention to the additive-combinatorial appendix. The chain framework, proper-chain lemmas, ladder-chain constructions for (ceil(k/2),1)-inseparable graphs, and the random graph phase transition all appear internally consistent. The reader's weakest-assumption analysis is accurate: the most exposed result is Theorem 7.3, an original proof that the authors admit could not be checked against a published construction. A failure there would remove only the dense-bipartite n^{3/2-o(1)} lower bounds (and Corollary 1.10 for some complete bipartite graphs), not the quadratic-abundance theorems. I also noted the Section 8 citation mismatch, but it is not load-bearing. Because the concern is lack of independent verification of a long appendix rather than a discovered contradiction, the appropriate verdict is CONDITIONAL, unchanged.","tokens_in":69729,"tokens_out":31079,"duration_ms":363885,"concrete_test":"Independently verify Theorem 7.3 by re-deriving Lemma A.7 and checking the two assertions that carry the proof: (1) after dividing a hypothetical F_d-solution by d^{j*}, the reduced tuple is a solution of E+ over B modulo q, and (2) this solution is nontrivial precisely because B avoids E+; in particular confirm that the only zero-sum proper submultisets of {γ1,γ2,1,-(γ1+γ2+1)} are empty, so 'trivial' forces all four variables equal. A second, cheap check is to instantiate the construction with small K, m, q and exhaustively search A for F_d-solutions; any counterexample would invalidate Theorems 7.13 and 1.8.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The dense bipartite lower bounds (Theorems 1.8 and 7.13) rest entirely on Theorem 7.3, whose proof in Appendix A is an original adaptation of Ruzsa's construction. The authors explicitly state (Section 7.1) that they could not recover the previously claimed K-fold Sidon construction; if this adapted proof has a hidden gap, the n^{3/2-o(1)} bounds for dense bipartite graphs would not follow. The most delicate step is Lemma A.7: a digit set A is built from B avoiding E+ (A.8), and any solution to an F_d equation is reduced, after dividing by d^{j*}, to a solution of E+ over B. The reduction depends on the coefficient ordering (A.9), on |E*|≤(2k2+1)q<d, and on the assertion that the reduced solution is nontrivial. I did not find an explicit error, but this chain of unverified dependencies is the weakest load-bearing point. Theorems 1.1, 1.2(1.3), and 6.6 do not depend on Theorem 7.3, so the paper's headline 'quadratic running times are abundant' is not endangered.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a general framework of chain constructions for lower bounds on the maximum H-bootstrap percolation running time M_H(n), and applies it to a wide range of graphs H. The main results include: a phase transition for H = G(k,p) around p = log k/k, with M_H(n) = O(1) below threshold and M_H(n) = Ω(n^2) above it; quadratic running times for all (⌈k/2⌉,1)-inseparable k-vertex graphs; almost quadratic running times for dense graphs and graphs containing the square of a Hamilton cycle; subquadratic upper and lower bounds for odd wheels; n^{3/2-o(1)} lower bounds for dense bipartite graphs; improved exponents for complete bipartite graphs; and superlinear lower bounds for all (2,1)-inseparable and (1,1,1)-inseparable graphs. Upper bounds are also proved, connecting M_H(n) to extremal numbers and to the Ruzsa-Szemerédi (6,3)-theorem.","tokens_in":69940,"tokens_out":31945,"duration_ms":373882,"significance":"If the results are correct, the paper substantially advances the field: it shows that quadratic maximum running times are abundant rather than clique-specific, establishes a sharp random-graph phase transition, and provides a unifying toolbox (proper chains, linking lemmas, ladder/dilation/line chains) that recovers and extends earlier constructions for cliques. The paper is honest about its one delicate point: the authors state in Section 7.1 that they could not recover an earlier claimed K-fold Sidon construction and instead prove an original adaptation (Theorem 7.3). The headline results, in particular Theorems 1.1, 1.2 and 6.6, do not depend on that additive construction, which is an important structural strength of the paper.","major_comments":[{"comment":"The inequality bounding |E*(b^(1), b^(2), b^(3), b^(4))| is not justified as written. For E*(x1,x2,x3,x4) = γ1x1 + γ2x2 + x3 − (γ1+γ2+1)x4, the sum of the absolute values of the coefficients is 2(γ1+γ2+1), so with only the stated bound γi ≤ k2 one obtains |E*(...)| ≤ 2(γ1+γ2+1)q ≤ (4k2+2)q. Since q is allowed to be as large as d/(4k2), this does not imply the claimed (2k2+1)q < d. This step is the one that converts a solution modulo d into an integer solution of an equation in E+, so Lemma A.7, and hence Theorem 7.3 and Theorem 1.8, rest on a statement that currently lacks a valid proof. The argument can likely be repaired by exploiting the parity and range restrictions on the αi to get stronger bounds on γ1 and γ2, or by choosing q slightly smaller, but the proof must be corrected. Given the authors' own remark in Section 7.1 that they could not recover the previously claimed K-fold Sidon construction, this point needs explicit verification.","section":"Appendix A, Lemma A.7"},{"comment":"The vertex count in the proof of Lemma 5.5 is incorrect: the linking procedure adds (s−1)(2k(k−2)−2) new vertices, not (τ−1)(2k(k−2)−2). The displayed inequality n + (τ−1)(2k(k−2)−2) ≤ 2k^2 n does not follow from τ ≤ n, and the proof does not state or use any bound on s = |A|. Since this lemma is used in every construction to turn a collection of chains into one proper chain on O(n) vertices, the statement needs to be repaired, for example by adding the assumption s ≤ n (which holds in all applications) and adjusting the constant, or by giving a separate bound on the number of chains.","section":"Section 5, Lemma 5.5"}],"minor_comments":[{"comment":"In the proof of Theorem 1.11, with m = ⌊n/150⌋ and |V| = 30m + 2, the assertion that 128|V| ≤ n is false (128·30m ≈ 25.6n). The Ω(n^{3/2}) lower bound is not affected because one can take m = cn for a sufficiently small absolute constant c, but the numerical inequality should be corrected.","section":"Section 6.3"},{"comment":"The statement of Theorem 8.3 gives no lower bound on |E(L)|, but the proof of Theorem 8.4 uses |E(L)| ≥ N/2^{2g} to obtain the claimed chain length. The statement should include that lower bound, which follows from the cited construction, or the proof of Theorem 8.4 should be adjusted accordingly.","section":"Section 8, Theorem 8.3"},{"comment":"In the sparsification argument for Theorem 1.9, the bound in (7.10) is for a fixed t, while (7.11) sums over roughly s values of t. The factor 1/(4r) should be replaced by 1/(4s), or the exponential decay of 2^{-r(s-1)} should be used explicitly, in order to justify the displayed lower bound on E|A'_q|.","section":"Section 7.6, equations (7.10)-(7.11)"},{"comment":"In the proof of Lemma 4.6, the references to 'property (1) of Definition 4.1' and 'property (2) of Definition 4.1' should refer to Definition 4.4, since the conditions used are the two conditions in the definition of a proper chain.","section":"Section 4, Lemma 4.6 proof"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong fit for a combinatorics journal and the main qualitative conclusions are likely correct. The headline quadratic and random-graph results rest on ladder-chain arguments that appear sound and are largely independent of the delicate additive construction. The main risk is isolated to Appendix A, specifically Lemma A.7 and its use in Theorem 7.3 for the dense bipartite lower bounds; the displayed inequality there is not justified as written. If the authors can correct Lemma A.7 and the small quantitative issues listed in the report, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read it cover to cover. The paper is the real thing. The main contribution is a general theory of proper chain constructions, which unifies the clique-specific chains from Bollobas et al. and Balogh et al. and then goes further. The highlight is Theorem 1.1: random graph H has MH(n)=O(1) below p=o(log k/k) and Omega(n^2) above p=omega(log k/k) — a crisp phase transition. The wheel results, the inseparable-graph superlinear bounds, and the connections to additive combinatorics (Behrend, Sidon, Ruzsa-Szemeredi) are all solid and put the field on much better footing. I was impressed by the honesty in Section 7.1: the authors say flat out that they could not reproduce the claimed K-fold Sidon construction and so they built their own variant. That kind of transparency is rare.\n\nWhere are the soft spots? The dense bipartite lower bounds (Theorems 1.8 and 7.13) rest entirely on Theorem 7.3, the new additive construction. The reader could not verify it, and neither could I from a careful read of Appendix A. The most delicate step is Lemma A.7, where the reduction to a modulo-d equation depends on coefficient ordering, the bound |E*| <= (2k2+1)q < d, and the assertion that the reduced solution is nontrivial. I did not find an explicit error, but this is a long chain of unverified dependencies sitting under an important theorem. The paper's headline claims — quadratic running times for inseparable graphs and the random graph phase transition — do not depend on Theorem 7.3, so those are safe. There is also a minor citation mismatch in Section 8 (the Lazebnik–Ustimenko–Woldar references don't line up cleanly with the stated theorem), but that is cosmetic.\n\nBottom line: this is a serious paper by serious people. It deserves a serious referee, and I would push the editor to have that referee spend extra time on Appendix A and Theorem 7.3. If that construction is independently verified, the paper becomes a cornerstone of the area. My own verdict is conditional: accept if the appendix is checked, not before. I'd bring it to the reading group and would likely cite the random graph phase transition regardless.","headline":"A genuinely general chain framework that settles when maximum running times are quadratic for many graphs; the only load-bearing risk is the new Ruzsa-type set construction behind the dense bipartite lower bounds.","tokens_in":70481,"tokens_out":2727,"would_cite":true,"duration_ms":30521,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C35","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Nearly every graph H makes its bootstrap percolation process run for a quadratic number of steps.","keywords":["graph bootstrap percolation","maximum running time","chain constructions","random graphs","additive combinatorics","Ruzsa-Szemerédi (6,3)-theorem","inseparable graphs","quadratic running time"],"falsifier":"Take a k-vertex graph H with δ(H) > 3k/4, such as the 5th power of a 40-cycle, build the ladder-chain starting graph from Section 6, and simulate the H-process for n around $10^{4}$; if the process stabilises in fewer than c·n² steps for an absolute constant c, then Theorem 6.6 fails. Alternatively, for a fixed prime p ≈ $10^{3}$, attempt to explicitly construct the solution-free set promised by Theorem 7.3; a failure there would signal a gap in the additive lemma behind the bipartite bounds.","tokens_in":69514,"feed_emoji":"⏳","tokens_out":7743,"duration_ms":87517,"temperature":0.7,"pith_summary":"This paper establishes that slow, quadratic maximum running times in graph bootstrap percolation are abundant, not a quirk of large cliques. It develops a general framework of chain constructions—sequences of overlapping copies of a fixed graph H that force an H-process to add one new edge per step—and applies it to random graphs, dense graphs, wheels, complete bipartite graphs, and inseparable graphs. In particular, a random k-vertex graph H = G(k,p) has M_H(n) = Ω(n²) once p = ω(log k/k), while below that threshold the running time is O(1); for any (⌈k/2⌉,1)-inseparable graph, M_H(n) = Ω(n²). Upper bounds, including the odd wheel's narrow subquadratic window M_{W_k}(n) = $n^{{2-o(1)}}$ and o(n²), connect the theory to extremal problems such as the Ruzsa–Szemerédi (6,3)-theorem.","feed_headline":"Quadratic percolation time is abundant among graphs","feed_subtitle":"A random test graph already forces the slowest possible process once its edges pass the connectivity threshold.","key_machinery":"The central object is the proper H-chain, a sequence of copies of H where consecutive copies meet at exactly one edge and no stray copy of H−e appears where it could shortcut the process; Lemma 4.6 turns a proper chain of length τ into a starting graph with running time at least τ. A linking lemma (Lemma 5.5) concatenates many short chains into one long chain. Three concrete chain families implement the machinery: ladder chains (copies placed with slopes across two long vertex sequences), dilation chains (vertex indices multiplied by elements of a modulo-p solution-free set, in non-bipartite and bipartite variants), and line chains (chains laid on edges of a high-girth linear hypergraph). The additive ingredient is a family of solution-free sets—Behrend-type sets for almost-quadratic bounds, and a new Ruzsa-type four-variable construction (Theorem 7.3) for the $n^{{3/2-o(1)}}$ bipartite bounds.","core_discovery":"The paper argues that the maximum running time M_H(n) of H-bootstrap percolation—the longest an H-process on n vertices can keep adding one edge per step—is quadratic for many more graphs than previously believed. Its central results: for random H = G(k,p), M_H(n) = Ω(n²) with high probability as soon as p = ω(log k/k), while below that threshold M_H(n) = O(1); for any k-vertex (⌈k/2⌉,1)-inseparable graph, M_H(n) = Ω(n²); for dense bipartite H with both sides' degrees above half, M_H(n) ≥ $n^{{3/2-o(1)}}$; and the odd wheel W_k gives a genuine intermediate regime M_{W_k}(n) = $n^{{2-o(1)}}$ and M_{W_k}(n) = o(n²). The framework also yields superlinear bounds ($n^{{1+2/(3k-2)}}$) for all inseparable graphs and connects the upper bounds to extremal problems such as the Ruzsa–Szemerédi (6,3)-theorem.","pith_inferences":["If the additive construction in Theorem 7.3 can be replaced by a genuine K-fold Sidon set construction, the bipartite lower bounds would likely approach the n^{2-1/r} upper bound much more closely; the parity-and-shift devices in Construction 7.9 are a workaround for a missing result in additive combinatorics.","The wheel's upper bound via the (6,3)-theorem hints that upper bounds for graphs with a Behrendian obstruction may generally be governed by induced-matching-type extremal problems; extending that link could give new upper bounds for other graphs H.","For random H with p = c log k/k for a fixed c > 1, the paper's proof should probably extend to give Ω(n²), while the range log k/(2k) < p < log k/k may admit intermediate exponents—a concrete computational target for small k.","The umbrella of proper chains suggests that the list of possible running times—constant, logarithmic, linear, n^{3/2-o(1)}, n^{2-o(1)}, and quadratic—is not yet complete; the framework may produce new exponents for other graph classes."],"forward_implications":["Random graphs: for H = G(k,p), the maximum running time switches from O(1) to Ω(n²) at the connectivity threshold log k/k, so almost all graphs have quadratic maximum running time even when their average degree is near-logarithmic.","Quadratic running time is guaranteed for every k-vertex graph that cannot be disconnected by deleting any one edge plus up to ⌈k/2⌉ of its vertices—in particular, for all graphs with minimum degree greater than 3k/4, generalising the known clique lower bounds.","The odd wheel W_k is the first example with both M_{W_k}(n) = n^{2-o(1)} and M_{W_k}(n) = o(n²), showing the almost-quadratic window is a real phenomenon and leaving the exact status of K_5 as a sharp open question.","Dense bipartite graphs have running time at least n^{3/2-o(1)}, and complete bipartite graphs K_{r,s} interpolate between this and the n^{2-1/r} upper bound; the cube graph Q_3 matches the best known extremal-number bounds up to a polynomial factor.","Every (2,1)-inseparable graph—one that survives deletion of any edge and two vertices—has superlinear maximum running time n^{1+2/(3k-2)}."],"supporting_citations":[{"why":"Supplies the earlier quadratic lower bounds for cliques K_k with k ≥ 6 and the initial chain-linking idea that the paper generalises into Lemma 5.5.","marker":"[3]"},{"why":"Introduces the chain method for explicit lower bounds on M_{K_k}(n) and the earlier conjecture that all K_k-processes have subquadratic running time, which this paper refutes in broad generality.","marker":"[7]"},{"why":"Provides Behrend's construction of large sets free of 3-term arithmetic progressions, used to obtain the n^{2-o(1)} lower bounds for graphs with strong minimum degree and for wheels.","marker":"[5]"},{"why":"Ruzsa's systematic study of sets avoiding solutions to linear equations supplies the method behind both the Behrend-type Theorem 7.2 and the four-variable construction of Theorem 7.3.","marker":"[35]"},{"why":"The Ruzsa–Szemerédi (6,3)-theorem is the crucial input for the upper bound M_{W_k}(n) = o(n²) for odd wheels.","marker":"[36]"},{"why":"The Kővári–Sós–Turán bound on the extremal number of complete bipartite graphs yields the general upper bound for bipartite H and the target shape n^{2-1/r}.","marker":"[24]"},{"why":"Bollobás's random graph facts supply the isolated-edge statement used for the O(1) side of the random-graph phase transition and the high-connectivity statements for the quadratic side.","marker":"[9]"},{"why":"The Kim–Sudakov–Vu asymmetry theorem gives a.a.s. self-stability of G(k,p), which the ladder-chain proof for random graphs needs.","marker":"[25]"},{"why":"Singer's Sidon set construction gives the large slope set used in the ladder-chain lower bound for the cube graph Q_3.","marker":"[38]"}],"fun_headline_variants":["Random graphs force quadratic percolation times","Chain constructions show quadratic running times broadly","Beyond cliques: many graphs slow percolation to max","Odd wheels yield intermediate percolation speed","Framework extends slow percolation to wide graph families"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The $n^{{3/2-o(1)}}$ lower bounds for dense bipartite graphs rest on Theorem 7.3, a new additive-combinatorics construction of large sets avoiding non-trivial solutions to certain four-variable equations; the authors note they could not recover an earlier claimed K-fold Sidon construction and adapted Ruzsa's method instead, so if that adaptation contains a hidden gap, the bipartite bounds would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Random graphs force quadratic percolation times","Chain constructions show quadratic running times broadly","Beyond cliques: many graphs slow percolation to max","Odd wheels yield intermediate percolation speed","Framework extends slow percolation to wide graph families"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000243,"raw_usage":{"total_tokens":1531,"prompt_tokens":947,"completion_tokens":584,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":563,"completion_tokens_details":{"reasoning_tokens":513}},"tokens_in":563,"tokens_out":584,"duration_ms":7773,"temperature":1.0,"reasoning_tokens":513,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T04:12:22.721225+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a k-vertex graph H with δ(H) > 3k/4, such as the 5th power of a 40-cycle, build the ladder-chain starting graph from Section 6, and simulate the H-process for n around $10^{4}$; if the process stabilises in fewer than c·n² steps for an absolute constant c, then Theorem 6.6 fails. Alternatively, for a fixed prime p ≈ $10^{3}$, attempt to explicitly construct the solution-free set promised by Theorem 7.3; a failure there would signal a gap in the additive lemma behind the bipartite bounds.","supporting_citations":[{"cited_title":"Bollob´ as, M","cited_arxiv_id":null,"evidence_quote":"Introduces the chain method for explicit lower bounds on M_{K_k}(n) and the earlier conjecture that all K_k-processes have subquadratic running time, which this paper refutes in broad generality."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Behrend's construction of large sets free of 3-term arithmetic progressions, used to obtain the n^{2-o(1)} lower bounds for graphs with strong minimum degree and for wheels."},{"cited_title":"Ruzsa, Solving a linear equation in a set of integers I , Acta Arithmetica 65 (1993), no","cited_arxiv_id":null,"evidence_quote":"Ruzsa's systematic study of sets avoiding solutions to linear equations supplies the method behind both the Behrend-type Theorem 7.2 and the four-variable construction of Theorem 7.3."},{"cited_title":"Z Ruzsa and E","cited_arxiv_id":null,"evidence_quote":"The Ruzsa–Szemerédi (6,3)-theorem is the crucial input for the upper bound M_{W_k}(n) = o(n²) for odd wheels."},{"cited_title":"T S´ os, and P","cited_arxiv_id":null,"evidence_quote":"The Kővári–Sós–Turán bound on the extremal number of complete bipartite graphs yields the general upper bound for bipartite H and the target shape n^{2-1/r}."},{"cited_title":"Bollob´ as,Random Graphs, 2nd ed., Cambridge University Press, 2001","cited_arxiv_id":null,"evidence_quote":"Bollobás's random graph facts supply the isolated-edge statement used for the O(1) side of the random-graph phase transition and the high-connectivity statements for the quadratic side."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Kim–Sudakov–Vu asymmetry theorem gives a.a.s. self-stability of G(k,p), which the ladder-chain proof for random graphs needs."},{"cited_title":"Singer, A theorem in finite projective geometry and some application s to number theory , Transactions of the American Mathematical Society 43 (1938), no","cited_arxiv_id":null,"evidence_quote":"Singer's Sidon set construction gives the large slope set used in the ladder-chain lower bound for the cube graph Q_3."}],"review_version":1}