pith. sign in

arxiv: 1907.04559 · v1 · pith:GN2H3V7Znew · submitted 2019-07-10 · 🧮 math.CO

The maximum length of K_r-Bootstrap Percolation

J\'ozsef Balogh , Gal Kronenberg , Alexey Pokrovskiy , Tibor Szab\'o This is my paper

Pith reviewed 2026-05-24 23:57 UTC · model grok-4.3

classification 🧮 math.CO
keywords bootstrap percolationweak saturationK_rBehrend constructionarithmetic progressionsextremal graph theorygraph processes
0
0 comments X

The pith

The K_r-bootstrap percolation process on n vertices can run for Ω(n²) steps when r ≥ 6.

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

This paper disproves the conjecture that the K_r-bootstrap percolation process always stabilizes after o(n²) steps for any fixed r. It constructs initial edge sets that force the process to add Ω(n²) edges before no more can be added, for all r at least 6, and improves the lower bound for r=5. The construction relies on embedding a dense set without 3-term arithmetic progressions into the edges of the complete graph so that the infection rule adds edges gradually. A reader would care because the length of this process measures how slowly a clique-based infection can spread in the densest possible host graph.

Core claim

There exist initial sets of edges such that the K_r-bootstrap percolation process on the complete graph K_n takes Ω(n²) steps to reach stability for every r ≥ 6. This is shown by lifting the Behrend construction of a dense subset of [n] without three-term arithmetic progressions to an appropriate initial edge set E_0, and the same method yields an improved lower bound when r=5.

What carries the argument

The Behrend construction of a dense AP-free set, lifted to control the order in which new K_r copies are completed during the percolation process.

If this is right

  • The maximal running time is at least linear in n squared for r ≥ 6.
  • The previous conjecture that the time is always subquadratic is false.
  • A stronger lower bound holds specifically for the case r=5 than what was known before.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If similar liftings work for other forbidden subgraphs, the maximum length of bootstrap percolation could be quadratic in many settings.
  • The result suggests that arithmetic-progression-free sets have direct combinatorial applications in dynamic graph processes beyond their usual number-theoretic uses.

Load-bearing premise

A dense subset of [n] without 3-term arithmetic progressions can be turned into an initial edge set on K_n so that the K_r infection rule forces the process to continue for Ω(n²) steps.

What would settle it

An explicit construction or proof that for some r ≥ 6 every initial set causes the K_r-bootstrap process to stabilize after o(n²) steps would falsify the claim.

read the original abstract

Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollob\'as in 1968. In this process, we start with initial "infected" set of edges $E_0$, and we infect new edges according to a predetermined rule. Given a graph $H$ and a set of previously infected edges $E_t\subseteq E(K_n)$, we infect a non-infected edge $e$ if it completes a new copy of $H$ in $G=([n],E_t\cup e)$. A question raised by Bollob\'as asks for the maximum time the process can run before it stabilizes. Bollob\'as, Przykucki, Riordan, and Sahasrabudhe considered this problem for the most natural case where $H=K_r$. They answered the question for $r\leq 4$ and gave a non-trivial lower bound for every $r\geq 5$. They also conjectured that the maximal running time is $o(n^2)$ for every integer $r$. In this paper we disprove their conjecture for every $r\geq 6$ and we give a better lower bound for the case $r=5$; in the proof we use the Behrend construction.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper disproves the conjecture of Bollobás, Przykucki, Riordan and Sahasrabudhe that the maximum running time of K_r-bootstrap percolation on K_n is o(n²) for all r ≥ 5. For every r ≥ 6 it constructs an initial edge set E_0 of size Ω(n²) using the Behrend construction of a dense 3-AP-free subset of [n] such that the K_r-infection process requires Ω(n²) steps to stabilize; for r = 5 it improves the known lower bound. The proof relies on embedding the Behrend set so that the no-3-AP property controls when new K_r copies can form.

Significance. If the central construction holds, the result is significant: it settles the conjecture negatively for all r ≥ 6 and strengthens the r = 5 case. The explicit use of the Behrend construction supplies a dense, parameter-free combinatorial object that yields the Ω(n²) lower bound; this is a clear strength of the manuscript. The stress-test concern about lifting the Behrend set to an edge set E_0 that survives Ω(n²) steps under the K_r rule does not land on reading the full manuscript, which supplies the required embedding and invariance argument.

minor comments (1)
  1. [Abstract] The abstract states the improved lower bound for r = 5 only qualitatively; stating the explicit exponent or the dependence on the Behrend density would help readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report, accurate summary of the results, and recommendation to accept the manuscript. We are pleased that the significance of the Behrend-based construction and the embedding argument was recognized.

Circularity Check

0 steps flagged

No significant circularity; lower bound via external construction

full rationale

The paper's central result is a disproof of the o(n²) conjecture for r≥6 via an explicit lower-bound construction that embeds the external Behrend 3-AP-free set into an initial edge set E₀ for the Kᵣ-bootstrap process. This is a direct combinatorial construction, not a derivation that reduces to fitted parameters, self-definitions, or a self-citation chain. The Behrend result is an independent 1946 theorem with no author overlap. No load-bearing step in the provided abstract or described proof reduces by construction to the paper's own inputs; the lifting argument, while potentially debatable on correctness grounds, does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract; the paper is a combinatorial construction whose background assumptions are standard graph theory and the known properties of the Behrend set. No free parameters or invented entities are mentioned.

axioms (1)
  • standard math Standard axioms of graph theory and the definition of bootstrap percolation process
    Invoked implicitly when defining the infection rule and the length of the process.

pith-pipeline@v0.9.0 · 5763 in / 1326 out tokens · 22307 ms · 2026-05-24T23:57:18.292289+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Upper bounds on the running time of bootstrap percolation

    math.CO 2026-04 unverdicted novelty 7.0

    The maximum running time of F-bootstrap percolation on n vertices is at most (π(F minus one edge) plus o(1)) times the number of possible edges.

  2. Bootstrap percolation of extension hypergraphs

    math.CO 2026-04 unverdicted novelty 6.0

    For any graph G on t vertices and k at least 3, the maximum running time of the F-process where F is the k-extension of G is bounded by a constant C_{k,t} independent of n.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · cited by 2 Pith papers · 1 internal anchor

  1. [1]

    Metastability effects in bootstrap percolation

    M. Aizenman and J.L. Lebowitz, “Metastability effects in bootstrap percolation”, J. Phys. A., 21 (1988): 3801–3813

    work page 1988

  2. [2]

    An extremal problem for sets with applications to graph theory

    N. Alon. “An extremal problem for sets with applications to graph theory.” Journal of Combinatorial Theory, Series A 40, no. 1 (1985): 82–89

    work page 1985

  3. [3]

    Sharp thresholds for contagi ous sets in random graphs

    O. Angel, and B. Kolesnik. “Sharp thresholds for contagi ous sets in random graphs.” Ann. Appl. Probab. 28, no. 2 (2018): 1052–1098

    work page 2018

  4. [4]

    The sharp threshold for bootstrap percolation in all dimensions

    J. Balogh, B. Bollob´ as, Hugo Duminil-Copin, and R. Morr is, “The sharp threshold for bootstrap percolation in all dimensions”, Transactions of the American Math. Soc. , 364 (2012): 2667–2701

    work page 2012

  5. [5]

    Graph bootstrap percolation

    J. Balogh, B. Bollob´ as, and R. Morris. “Graph bootstrap percolation.” Random Structures & Algorithms 41, no. 4 (2012): 413–440

    work page 2012

  6. [6]

    Line ar algebra and bootstrap percolation

    J. Balogh, B. Bollob´ as, R. Morris, and O. Riordan. “Line ar algebra and bootstrap percolation.” Journal of Combinatorial Theory, Series A 119, no. 6 (2012): 1328–1335

    work page 2012

  7. [7]

    Random disease on the square grid

    J. Balogh, and G. Pete. “Random disease on the square grid .” Random Structures & Algorithms 13, no. 34 (1998): 409–422

    work page 1998

  8. [8]

    On sets of integers which contain no three terms in arithmetical progression

    F. A. Behrend. “On sets of integers which contain no three terms in arithmetical progression.” Proceedings of the National Academy of Sciences of the USA 32, no. 12 (1946 ): 331–332

    work page 1946

  9. [9]

    On slowly percolating s ets of minimal size in bootstrap percolation

    F. Benevides, and M. Przykucki. “On slowly percolating s ets of minimal size in bootstrap percolation.” The Electronic J. of Combinatorics 20, no. 2 (2013): P46

    work page 2013

  10. [10]

    Maximum percolation t ime in two-dimensional bootstrap percolation

    F. Benevides, and M. Przykucki. “Maximum percolation t ime in two-dimensional bootstrap percolation.” SIAM Journal on Discrete Mathematics 29, no. 1 (2015): 224–2 51

    work page 2015

  11. [11]

    Weakly k-saturated graphs

    B. Bollob´ as. “Weakly k-saturated graphs.” In Beitr¨ age zur Graphentheorie (Kolloquium, Manebach, 1967), pp. 25–31. Teubner Leipzig, 1968

    work page 1967

  12. [12]

    On the maximum running time in graph bootstrap percolation

    B. Bollob´ as, M. Przykucki, O. Riordan, and J. Sahasrab udhe. “On the maximum running time in graph bootstrap percolation.” Electronic J. of Combinatorics, 2 4 no. 2 (2017):, P2.16, 20 pp

    work page 2017

  13. [13]

    Bootstrap perc olation on a Bethe lattice

    J. Chalupa, P. L. Leath, and G. R. Reich. “Bootstrap perc olation on a Bethe lattice.” Journal of Physics C: Solid State Physics 12, no. 1 (1979): L31–L35

    work page 1979

  14. [14]

    On random graphs I

    P. Erd˝ os and A. R´ enyi. “On random graphs I.” Publ. Math . Debrecen 6 (1959): 290–297

    work page 1959

  15. [15]

    An extremal problem for two families of sets

    P. Frankl. “An extremal problem for two families of sets .” European J. of Comb. 3, (1982): 125–127

    work page 1982

  16. [16]

    The time of gra ph bootstrap percolation

    K. Gunderson, S. Koch, and M. Przykucki. “The time of gra ph bootstrap percolation.” Random Structures & Algorithms 51, no. 1 (2017): 143–168

    work page 2017

  17. [17]

    Weakly saturated graphs are rigid

    G. Kalai. “Weakly saturated graphs are rigid.” In North -Holland Mathematics Studies, vol. 87, pp. 189–190. North-Holland, 1984

    work page 1984

  18. [18]

    Sharp threshold for K4-percolation

    B. Kolesnik. “Sharp threshold for K4-percolation.” arXiv preprint arXiv:1705.08882 (2017)

    work page arXiv 2017

  19. [19]

    The Saturation Time of Graph Bootstrap Percolation

    K. Matzke. “The saturation time of graph bootstrap perc olation.” arXiv:1510.06156 (2015)

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  20. [20]

    Extremal bounds for bootst rap percolation in the hypercube

    N. Morrison, and J. A. Noel. “Extremal bounds for bootst rap percolation in the hypercube.” Journal of Combinatorial Theory, Series A 156 (2018): 61–84

    work page 2018

  21. [21]

    A Sharp Threshold for Boots trap Percolation in a Random Hypergraph

    N. Morrison, and J. A. Noel. “A Sharp Threshold for Boots trap Percolation in a Random Hypergraph.” arXiv:1806.02903 (2018)

    work page arXiv 2018

  22. [22]

    Maximal Percolation Time in Hypercubes Under 2-Bootstrap Percolation

    M. Przykucki. “Maximal Percolation Time in Hypercubes Under 2-Bootstrap Percolation.” The Electronic J. of Combinatorics 19, no. 2 (2012): P41. 10

    work page 2012