pith. sign in

arxiv: 2605.15066 · v1 · pith:576XC73Fnew · submitted 2026-05-14 · 🧮 math.PR · math.CO

The critical activation density in graph bootstrap percolation

Brett Kolesnik , Tam\'as Makai , Rajko Nenadov , Xavier P\'erez-Gim\'enez , Pawe{\l} Pra{\l}at , Maksim Zhukovskii This is my paper

Pith reviewed 2026-05-15 02:57 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords bootstrap percolationErdős–Rényi graphscritical thresholdactivation densitygraph Hpercolation process
0
0 comments X

The pith

For every graph H the critical H-percolation threshold p_c(n,H) is located in terms of the limiting density ρ(H) of the graphs that activate an edge most efficiently.

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

The paper determines the exact critical threshold at which an Erdős–Rényi random graph G(n,p) becomes fully activated under the bootstrap rule defined by an arbitrary fixed graph H. An edge activates precisely when it is the single missing edge in some copy of H whose other edges are already active. By introducing the parameter ρ(H) as the critical limiting density of the minimal subgraphs that achieve activation of a given edge, the authors give the location of p_c(n,H) for every H. This unifies and improves earlier special-case results for triangles and K4 while answering a question of Balogh, Bollobás and Morris. A sympathetic reader cares because the same density parameter controls whether the threshold is sharp and how the behavior changes when H varies.

Core claim

In graph bootstrap percolation, the process H-percolates with high probability precisely when the initial edge probability p exceeds the threshold determined by the critical limiting density ρ(H) of the graphs that most efficiently activate a given edge. This location holds for every fixed graph H and recovers the classical connectivity threshold when H is a triangle.

What carries the argument

The critical limiting density ρ(H), which measures the infimum asymptotic density of graphs that activate a target edge under the H-rule.

Load-bearing premise

That the critical limiting density ρ(H) of the most efficient activating graphs is well-defined and finite for every graph H, and that this single quantity determines the percolation threshold.

What would settle it

A specific graph H together with a calculation or simulation showing that the observed percolation threshold deviates from the value predicted by its ρ(H).

read the original abstract

In graph bootstrap percolation, edges of an Erd\H{o}s-R\'enyi random graph ${\mathcal G}_{n,p}$ are initially active. Activation spreads to other edges of the complete graph $K_n$ by an iterative process governed by a fixed graph $H$, whereby an edge becomes active whenever it is the only inactive edge in a copy of $H$. If all edges of $K_n$ are eventually activated, we say the process $H$-percolates. The case $H=K_3$ corresponds to the classical sharp threshold for connectivity in ${\mathcal G}_{n,p}$. When $H=K_4$, there are close connections with $2$-neighbor bootstrap percolation from statistical physics. Varying $H$ produces a wide range of behaviors. In this work, for every graph $H$, we locate the critical $H$-percolation threshold $p_c(n,H)$, answering a question of Balogh, Bollob\'as, and Morris. Our general methods recover and improve several previous results. The location of $p_c(n,H)$ is related to a critical limiting density $\rho(H)$ of graphs that most efficiently activate a given edge. Introducing the parameter $\rho(H)$ raises several questions. For instance, it remains open whether $\rho(H)$ is computable in general, and its expression appears to indicate when the $H$-percolation threshold is sharp.

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

3 major / 2 minor

Summary. The paper claims that for every fixed graph H, the critical threshold p_c(n,H) for H-bootstrap percolation on G(n,p) (where an edge activates if it completes a copy of H with all other edges active) is determined by a quantity ρ(H), defined as the infimum of the limiting edge-to-vertex densities among graphs that most efficiently activate a given edge under iterated H-bootstrap. This locates the threshold asymptotically and recovers/improves prior results for H = K_3 and H = K_4.

Significance. If the claims hold, the work supplies a general location for the H-percolation threshold across all H, resolving a question of Balogh, Bollobás, and Morris. The parameter ρ(H) provides a uniform framework that may also characterize sharpness of the threshold; the methods appear to extend to related bootstrap processes in random graphs.

major comments (3)
  1. [§2] §2, Definition of ρ(H): the infimum over limiting densities of minimal activating graphs is asserted to be positive and finite for every H and to control the threshold, but no compactness argument, uniform lower bound, or proof that the infimum is attained is supplied; this is load-bearing for the location formula when H contains high-girth or asymmetric substructures.
  2. [Theorem 1.1] Theorem 1.1 (location of p_c(n,H)): the expression p_c(n,H) ∼ n^{-1/ρ(H)} (or equivalent) assumes that the minimal-density activators dominate the global percolation probability, yet the argument sketch does not rule out contributions from higher-density structures or show that the critical window is governed solely by ρ(H).
  3. [§4] §4 (proof sketch): the reduction from the activation process to the density ρ(H) lacks an explicit error analysis or verification that the infimum is realized by a sequence of finite graphs whose activation behavior scales to the n-vertex case.
minor comments (2)
  1. [§1] Notation for the iterative activation rule could be illustrated with a small explicit example (e.g., H = K_4) to clarify the process before the general definition.
  2. [Abstract] The abstract states that ρ(H) 'appears to indicate when the threshold is sharp,' but the manuscript does not supply a precise criterion or theorem linking ρ(H) to sharpness; this should be stated explicitly or removed.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough reading and for identifying points where additional justification and detail would strengthen the manuscript. We have revised the paper to address each of the three major comments, adding a compactness argument for ρ(H), expanding the domination argument in the proof of Theorem 1.1, and supplying explicit error bounds in the reduction. The changes appear in the new Section 2.3, the expanded proof of Theorem 1.1, and the detailed analysis now in §4. We believe these revisions resolve the concerns while preserving the original claims.

read point-by-point responses

  1. Referee: §2, Definition of ρ(H): the infimum over limiting densities of minimal activating graphs is asserted to be positive and finite for every H and to control the threshold, but no compactness argument, uniform lower bound, or proof that the infimum is attained is supplied; this is load-bearing for the location formula when H contains high-girth or asymmetric substructures.

    Authors: We agree that the original presentation of ρ(H) was too terse. In the revised manuscript we introduce a new subsection (2.3) that treats the set of all finite graphs that activate a distinguished edge under H-bootstrap as a sequence in the space of graphons. By compactness of the graphon space we obtain that the infimum is attained by a limiting graphon; the corresponding density is therefore realized. Positivity of ρ(H) follows from a uniform lower bound: any activating graph must contain at least one copy of H and therefore has edge density at least 1/(v(H)−1), which is positive and depends only on H. We have added Lemma 2.7 stating these facts explicitly and verifying that the same lower bound holds uniformly for all H with a fixed number of vertices. revision: yes

  2. Referee: Theorem 1.1 (location of p_c(n,H)): the expression p_c(n,H) ∼ n^{-1/ρ(H)} (or equivalent) assumes that the minimal-density activators dominate the global percolation probability, yet the argument sketch does not rule out contributions from higher-density structures or show that the critical window is governed solely by ρ(H).

    Authors: The proof of Theorem 1.1 already contains a first-moment calculation showing that any activator with density strictly larger than ρ(H) produces an activation probability that is o(1) at the scale p = n^{-1/ρ(H)−ε}. We have now made this comparison quantitative by inserting a union bound over a discretization of possible densities together with a second-moment argument that controls the variance of the number of minimal-density activators. The resulting calculation shows that the contribution of all higher-density structures is negligible compared with the main term coming from density ρ(H), thereby confirming that the threshold location is determined solely by ρ(H). The critical window statement is likewise strengthened by an explicit variance bound now appearing after the proof of Theorem 1.1. revision: yes

  3. Referee: §4 (proof sketch): the reduction from the activation process to the density ρ(H) lacks an explicit error analysis or verification that the infimum is realized by a sequence of finite graphs whose activation behavior scales to the n-vertex case.

    Authors: We accept that the sketch in the original §4 omitted quantitative error terms. The revised version replaces the sketch with a complete argument that proceeds in three steps: (i) for every ε>0 we select a finite activating graph G_ε whose density is at most ρ(H)+ε (existence follows from the compactness argument added in §2); (ii) we embed many copies of G_ε into G(n,p) and bound the probability that a given copy fails to activate by an explicit exponential tail; (iii) we apply a Chernoff-type concentration inequality to show that the total number of successful activations is concentrated around its expectation, with an error that vanishes as n→∞ uniformly in the choice of ε. The resulting error analysis appears as the new Proposition 4.3 and is used directly in the proof of the main threshold statement. revision: yes

Circularity Check

0 steps flagged

No circularity: ρ(H) defined independently; threshold relation does not reduce to input by construction

full rationale

The paper introduces ρ(H) as the infimum of limiting edge densities over graphs that activate a fixed edge via iterated H-bootstrap percolation, then locates p_c(n,H) in terms of this quantity. No quoted equation or step shows the threshold expression equaling a fitted parameter, a self-citation chain, or a renamed input; the definition of ρ(H) stands apart from the claimed location formula, and the derivation is presented as self-contained for arbitrary H. Potential gaps in proving ρ(H) is finite and attained are questions of proof strength, not circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the existence of ρ(H) as a well-defined infimum over activation graphs and on standard asymptotic properties of the Erdős–Rényi model and bootstrap process.

axioms (1)
  • standard math Standard properties of Erdős–Rényi random graphs G(n,p) and the iterative activation rule for bootstrap percolation
    Invoked throughout to define percolation and thresholds.
invented entities (1)
  • ρ(H) no independent evidence
    purpose: Critical limiting density of graphs that most efficiently activate a given edge
    Defined to express the threshold p_c(n,H); no independent evidence supplied in abstract.

pith-pipeline@v0.9.0 · 5583 in / 1198 out tokens · 40456 ms · 2026-05-15T02:57:30.338857+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Aizenman and J

    M. Aizenman and J. L. Lebowitz,Metastability effects in bootstrap percolation, J. Phys. A21(1988), no. 19, 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, J. Combin. Theory Ser. A40(1985), no. 1, 82–89

    work page 1985

  3. [3]

    Vertical Alveolar Ridge Augmentation in Implant Dentistry: A Surgical Manual and Horizontal Alveolar Ridge Augmentation in Implant Dentistry: A Surgical Manual. Tolstunov L, ed. Hoboken, NJ: John Wiley & Sons, Inc. Hoboken, New Jersey

    N. Alon and J. H. Spencer,The probabilistic method, fourth ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016

    work page 2016

  4. [4]

    Angel and B

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

    work page 2018

  5. [5]

    ,Large deviations for subcritical bootstrap percolation on the Erd˝ os–Rényi graph, J. Stat. Phys.185(2021), no. 2, Paper No. 8, 16

    work page 2021

  6. [6]

    Ascoli and X

    R. Ascoli and X. He,Rational values of the weak saturation limit, preprint (2026), available at arXiv:2501.15686

    work page arXiv 2026

  7. [7]

    Balister, B

    P. Balister, B. Bollobás, R. Morris, and P. Smith,Universality for monotone cellular automata, J. Eur. Math. Soc. (JEMS), to appear, available at arXiv:2203.13806

    work page arXiv

  8. [8]

    Graph bootstrap percolation

    J. Balogh, B. Bollobás, and R. Morris,Graph bootstrap percolation, Random Structures Algorithms41(2012), no. 4, 413–440

    work page 2012

  9. [9]

    Weakly saturated random graphs

    Z. Bartha and B. Kolesnik,Weakly saturated random graphs, Random Structures Algorithms65(2024), no. 1, 131–148

    work page 2024

  10. [10]

    H-percolation with a random H

    Z. Bartha, B. Kolesnik, and G. Kronenberg, H-percolation with a random H, Electron. Commun. Probab.29(2024), Paper No. 33, 5

    work page 2024

  11. [11]

    Bartha, B

    Z. Bartha, B. Kolesnik, G. Kronenberg, and Y . Peled,Sharp Fuss–Catalan thresholds in graph bootstrap percolation, preprint (2025), available at arXiv:2510.26724

    work page arXiv 2025

  12. [12]

    On $$K_{2,t}$$-Bootstrap Percolation

    M. Bidgoli, A. Mohammadian, and B. Tayfeh-Rezaie,On K2,t-bootstrap percolation, Graphs Combin.37(2021), no. 3, 731–741

    work page 2021

  13. [13]

    Beiträge zur Graphentheorie. (Internationales Kolloquium in Manebach vom 9.‐ 12. Mai 1967). 394 S. m. Abb. Leipzig 1968. B. G. Teubner Verlagsgesellschaft. Preis brosch. 15, 50 M .

    B. Bollobás,Weakly k-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), Teubner, Leipzig, 1968, pp. 25–31

    work page 1967

  14. [14]

    LINGUISTICS: THE CAMBRIDGE SURVEY: VOL. I. LINGUISTIC THEORY: FOUNDATIONS. Frederick J. Newmeyer (Ed.). Cambridge: Cambridge University Press, 1988. Pp. x+500. $49.50. - LINGUISTICS: THE CAMBRIDGE SURVEY: VOL. II. LINGUISTIC THEORY: EXTENSIONS AND IMPLICATIONS. Frederick J. Newmeyer (Ed.). Cambridge: Cambridge University Press, 1988. Pp. viii+320. $39.50. - LINGUISTICS: THE CAMBRIDGE SURVEY: VOL. III. LANGUAGE: PSYCHOLOGICAL AND BIOLOGICAL ASPECTS. Frederick J. Newmeyer (Ed.). Cambridge: Cambridge University Press, 1988. Pp. ix+350. $39.50.

    ,Random graphs, second ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001

    work page 2001

  15. [15]

    Chalupa, P

    J. Chalupa, P. L. Leath, and G. R. Reich,Bootstrap percolation on a bethe lattice, J. Phys. C21(1979), L31–L35

    work page 1979

  16. [16]

    Erd˝os, A

    P. Erd˝os, A. Hajnal, and J. W. Moon,A problem in graph theory, Amer. Math. Monthly 71(1964), 1107–1110

    work page 1964

  17. [17]

    An Extremal Problem for two Families of Sets

    P. Frankl,An extremal problem for two families of sets, European J. Combin.3(1982), no. 2, 125–127

    work page 1982

  18. [18]

    Friedgut,Sharp thresholds of graph properties, and the k-sat problem, J

    E. Friedgut,Sharp thresholds of graph properties, and the k-sat problem, J. Amer. Math. Soc.12(1999), no. 4, 1017–1054, With an appendix by Jean Bourgain

    work page 1999

  19. [19]

    Gardner,Mathematical games: The fantastic combinations of John Conway’s new solitaire game “life”, Sci

    M. Gardner,Mathematical games: The fantastic combinations of John Conway’s new solitaire game “life”, Sci. Am.223(1970), no. 4, 120–123

    work page 1970

  20. [20]

    Wiley‐Interscience Series in Discrete Mathematics and Optimization

    S. Janson, T. Łuczak, and A. Rucinski,Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000

    work page 2000

  21. [21]

    Weakly Saturated Graphs are Rigid

    G. Kalai,Weakly saturated graphs are rigid, Convexity and graph theory (Jerusalem, 1981), North-Holland Math. Stud., vol. 87, North-Holland, Amsterdam, 1984, pp. 189– 190

    work page 1981

  22. [22]

    Hyperconnectivity of graphs

    ,Hyperconnectivity of graphs, Graphs Combin.1(1985), no. 1, 65–79

    work page 1985

  23. [23]

    The sharp K4-percolation threshold on the Erdős–Rényi random graph

    B. Kolesnik,The sharp K4-percolation threshold on the Erd˝ os–Rényi random graph, Electron. J. Probab.27(2022), Paper No. 13, 23. 30 KOLESNIK, MAKAI, NENADOV, PÉREZ-GIMÉNEZ, PRAŁAT, AND ZHUKOVSKII

    work page 2022

  24. [24]

    P. J. Cameron, Combinatorial Surveys (Proceedings of the Sixth British Combinatorial Conference, Academic Press, 1977.)

    L. Lovász,Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977), Academic Press, London-New York, 1977, pp. 45–86

    work page 1977

  25. [25]

    Monotone cellular automata

    R. Morris,Monotone cellular automata, Surveys in combinatorics 2017, London Math. Soc. Lecture Note Ser., vol. 440, Cambridge Univ. Press, Cambridge, 2017, pp. 312–371

    work page 2017

  26. [26]

    Counting extensions

    J. Spencer,Counting extensions, J. Combin. Theory Ser. A55(1990), no. 2, 247–255

    work page 1990

  27. [27]

    Weak saturation in graphs: A combinatorial approach

    N. Terekhov and M. Zhukovskii,Weak saturation in graphs: a combinatorial approach, J. Combin. Theory Ser. B172(2025), 146–167

    work page 2025

  28. [28]

    Weak saturation rank: a failure of the linear algebraic approach to weak saturation

    ,Weak saturation rank: a failure of the linear algebraic approach to weak saturation, Combinatorica45(2025), no. 5, Paper No. 45, 18

    work page 2025

  29. [29]

    The International Congress of Mathematicians: Cambridge, MA, 1950

    S. Ulam,Random processes and transformations, Proceedings of the International Congress of Mathematicians, Vol. 2, Cambridge, Mass., 1950, pp. 264–275

    work page 1950

  30. [30]

    Alternative Schools in Korea

    J. von Neumann,Theory of self-reproducing automata, University of Illinois Press, Champaign, IL, USA, 1966. UNIVERSITY OFWARWICK, DEPARTMENT OFSTATISTICS Email address:brett.kolesnik@warwick.ac.uk LMU MUNICH, DEPARTMENT OFMATHEMATICS Email address:makai@math.lmu.de UNIVERSITY OFCANTERBURY, SCHOOL OFMATHEMATICS ANDSTATISTICS Email address:rajko.nenadov@can...

    work page 1966