pith. sign in

arxiv: 2604.22630 · v1 · submitted 2026-04-24 · 🧮 math.CO

Upper bounds on the running time of bootstrap percolation

Weichan Liu , Xiangxiang Nie , Sim\'on Piga , Bjarne Sch\"ulke This is my paper

Pith reviewed 2026-05-08 11:03 UTC · model grok-4.3

classification 🧮 math.CO
keywords bootstrap percolationhypergraphsTurán densityrunning timeextremal hypergraph theoryk-uniform graphsupper bounds
0
0 comments X

The pith

The maximum running time of any F-bootstrap percolation process is at most (π(F−e) + o(1)) times the total number of possible k-edges.

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

The paper proves that for any k-uniform hypergraph F and any edge e inside F, the longest possible F-bootstrap percolation process on n vertices adds at most the Turán density of the hypergraph F minus e, plus a vanishing error term, times all possible k-subsets. This supplies the first non-trivial upper bound on the maximum running time M_F(n) for many families, including complete k-graphs K_t where the fraction simplifies to (t-3)/(t-2) for t at least 3. A reader cares because these processes describe cascading completions in combinatorial structures, and the bound converts classical extremal densities into concrete limits on how long the cascade can last.

Core claim

For every k ≥ 2, every k-graph F, and every edge e in F, the maximum running time satisfies M_F(n) ≤ (π(F−e) + o(1)) binom(n,k). In particular this yields M_{K_t}(n) ≤ ((t−3)/(t−2) + o(1)) binom(n,2) for t ≥ 3, improving the previous trivial bound of binom(n,2). The argument relates each step of the iterative edge-addition process to the extremal density of F−e.

What carries the argument

The Turán density π(H) of a k-graph H, the limit of the maximum edge density in an H-free k-graph on n vertices. It limits the total number of edges that can be added before the process must stabilize.

If this is right

  • The bound is strictly less than the total number of edges whenever π(F−e) < 1.
  • For every complete graph K_t with t ≥ 3 the running time is at most a fixed fraction (t−3)/(t−2) of all possible pairs.
  • The same density bound applies uniformly to every possible starting configuration H0.
  • The result extends immediately from graphs to arbitrary k-uniform hypergraphs F.

Where Pith is reading between the lines

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

  • When the exact value of π(F−e) is known, the leading term of the running-time bound is asymptotically determined by extremal theory.
  • The same density argument may adapt to study the typical rather than worst-case duration of the process.
  • Similar density-controlled bounds could apply to other iterative completion processes in hypergraphs or in random settings.

Load-bearing premise

That the Turán density of F minus one edge suffices to bound the entire iterative sequence of edge additions without extra stability or supersaturation conditions that could fail for some F.

What would settle it

An explicit family of initial hypergraphs H0 on n vertices where the F-process requires strictly more than (π(F−e) + ε) binom(n,k) steps for some fixed ε > 0 and infinitely many n.

read the original abstract

For $k$-graphs $F$ and $H_0$ the $F$-bootstrap percolation process (or $F$-process) starting with $H_0$ is a sequence $(H_i)_{i\geq0}$ of $k$-graphs such that $H_{i+1}$ is obtained from $H_i$ by adding all those $e\in V(H_0)^{(k)}\setminus E(H_i)$ as edges that complete a new copy of $F$. The running time of this $F$-process, denoted by $M_F(H_0)$, is the smallest $i$ with $H_i=H_{i+1}$. Bollob\'as proposed the problem of determining the maximum running time for $n\in\mathbb{N}$, i.e., $M_F(n)=\max_{\vert V(H_0)\vert=n}M_F(H_0)$. Although this problem has received a lot of attention recently, until now the best known upper bound for $M_{K_t}(n)$, with $t\geq5$, was the trivial bound $\binom{n}{2}$. Here we provide the first non-trivial upper bound for this problem by showing that $$M_{K_t}(n)\leq\Big(\frac{t-3}{t-2}+o(1)\Big)\binom{n}{2}$$ holds for every integer $t\geq 3$. In fact, we prove the following more general result. For every $k\geq2$, every $k$-graph $F$, and every $e\in E(F)$ we have $M_F(n)\leq\big(\pi(F-e)+o(1)\big)\binom{n}{k}$, where $\pi$ is the Tur\'an density.

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

1 major / 2 minor

Summary. The manuscript studies the maximum running time M_F(n) of the F-bootstrap percolation process on n-vertex k-graphs. It proves that for every k≥2, every k-graph F, and every edge e in F, M_F(n) ≤ (π(F−e) + o(1)) binom(n,k), where π denotes the Turán density. As a corollary for cliques, it obtains the first non-trivial upper bound M_{K_t}(n) ≤ ((t−3)/(t−2) + o(1)) binom(n,2) for t≥3, improving on the trivial bound binom(n,2) for t≥5.

Significance. If correct, the result supplies the first non-trivial upper bounds on bootstrap percolation running times by linking them directly to Turán densities, a connection that could enable further progress via extremal methods. The generality to arbitrary F (rather than only cliques) and the explicit improvement for K_t are strengths; the manuscript ships a clean, falsifiable statement that is parameter-free in its leading term.

major comments (1)
  1. [Proof of the general upper bound] The central argument (in the section proving the general theorem) constructs an auxiliary (F−e)-free k-graph with one edge per percolation round whose size is bounded by ex(n, F−e). To obtain the contradiction when the density exceeds π(F−e), it must be shown that any copy of F−e in this auxiliary graph cannot arise under the addition order of the process. For arbitrary F this step appears to require either supersaturation (many copies) or stability (structure close to the Turán graph) to guarantee the required contradiction; neither is known to hold uniformly. Please identify the precise location where this is established and whether the argument avoids these tools or invokes them implicitly.
minor comments (2)
  1. [Abstract] The abstract states the K_t corollary before the general theorem; reversing the order would better reflect the logical structure.
  2. [Introduction] Notation for the running time M_F(H_0) versus M_F(n) is introduced clearly, but the o(1) term should be made explicit as n→∞ in the statement of the main theorem.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive feedback on the proof of the general upper bound. We address the major comment below, providing the requested location and clarification on the argument's structure.

read point-by-point responses

  1. Referee: [Proof of the general upper bound] The central argument (in the section proving the general theorem) constructs an auxiliary (F−e)-free k-graph with one edge per percolation round whose size is bounded by ex(n, F−e). To obtain the contradiction when the density exceeds π(F−e), it must be shown that any copy of F−e in this auxiliary graph cannot arise under the addition order of the process. For arbitrary F this step appears to require either supersaturation (many copies) or stability (structure close to the Turán graph) to guarantee the required contradiction; neither is known to hold uniformly. Please identify the precise location where this is established and whether the argument avoids these tools or invokes them implicitly.

    Authors: The proof of the general upper bound appears in Section 3, Theorem 3.2 (the statement M_F(n) ≤ (π(F−e) + o(1)) binom(n,k)). The auxiliary k-graph G is defined in the first paragraph of the proof by selecting, for each round i of the process, exactly one edge that is added in that round; the construction ensures |E(G)| equals the running time. We then argue directly that G must be (F−e)-free: suppose for a contradiction that G contains a copy of F−e on some vertex set. By the definition of the F-process, the edges of this copy in G correspond to distinct rounds, so the last edge added in the process on those vertices would complete a copy of F (since F−e plus the final edge yields F). But the process adds all such completing edges simultaneously in a single round, contradicting that the selected edges come from distinct rounds. This yields the desired (F−e)-freeness without any appeal to supersaturation or stability. The size bound |E(G)| ≤ ex(n, F−e) is then immediate, and the o(1) term follows from the definition of the Turán density π(F−e). The argument is elementary and holds for arbitrary F; it uses only the sequential nature of the process and the maximality of the running time. We agree that the exposition of this step could be expanded for clarity and will add a short explanatory remark (and possibly a small diagram) in the revised manuscript. revision: partial

Circularity Check

0 steps flagged

No circularity; bound uses independent Turán density on separately defined running time

full rationale

The paper defines M_F(n) as the maximum number of iterations in the F-bootstrap percolation process over initial k-graphs on n vertices, a quantity independent of extremal densities. The claimed inequality M_F(n) ≤ (π(F−e) + o(1)) binom(n,k) expresses this maximum in terms of the standard Turán density π(F−e), which is defined externally as the asymptotic maximum density of (F−e)-free k-graphs. No step in the abstract reduces the running-time quantity to a fitted parameter, a self-referential definition, or a load-bearing self-citation; the result is presented as a theorem proved from the process definition and extremal graph theory. This is the most common honest non-finding for papers that bound one combinatorial process using an unrelated extremal parameter.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the existence and basic properties of Turán density together with the iterative definition of the bootstrap process; no new entities are introduced and no parameters are fitted to data.

axioms (2)
  • standard math The Turán density π(G) exists for every fixed graph or hypergraph G.
    Invoked when the bound is stated in terms of π(F−e).
  • domain assumption The bootstrap percolation process is well-defined and terminates after finitely many steps on finite vertex sets.
    Used to define the running time M_F(H_0) as the smallest i with H_i = H_{i+1}.

pith-pipeline@v0.9.0 · 5627 in / 1482 out tokens · 52136 ms · 2026-05-08T11:03:34.830434+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

20 extracted references · 8 canonical work pages · 1 internal anchor

  1. [1]

    Balogh, B

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

    2012

  2. [2]

    Balogh, G

    J. Balogh, G. Kronenberg, A. Pokrovskiy, and T. Szabó,The maximum length ofKr-Bootstrap Percolation, arXiv:1907.04559 (2019), To appear in Proc. Amer. Math. Soc.Ò 1

    work page arXiv 1907

  3. [3]

    Bollobás,Weakly k-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), B

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

    1967

  4. [4]

    Bollobás, M

    B. Bollobás, M. Przykucki, O. Riordan, and J. Sahasrabudhe,On the maximum running time in graph bootstrap percolation, Electron. J. Combin.24(2017), no. 2, P2.16.Ò 1

    2017

  5. [5]

    Chalupa, P

    J. Chalupa, P. L. Leath, and G. R. Reich,Bootstrap percolation on a Bethe lattice, J. Phys. C: Solid State Phys.12(1979), no. 1, L31.Ò 1

    1979

  6. [6]

    Erdős and M

    P. Erdős and M. Simonovits,A limit theorem in graph theory, Studia Sci. Math. Hungar.1(1966), 51–57.Ò 1

    1966

  7. [7]

    Erdős and A

    P. Erdős and A. H. Stone,On the structure of linear graphs, Bull. Amer. Math. Soc.52(1946), 1087–1091.Ò 1

    1946

  8. [8]

    Espuny Díaz, B

    A. Espuny Díaz, B. Janzer, G. Kronenberg, and J. Lada,Long running time for hypergraph bootstrap percolation, arXiv:2209.02015 (2022), To appear in European J. Combin.Ò 1

    work page arXiv 2022

  9. [9]

    Fabian, P

    D. Fabian, P. Morris, and T. Szabó,Slow graph bootstrap percolation III: Chain constructions, arXiv:2508.03835 (2025).Ò 1 , 1.3

    work page arXiv 2025

  10. [10]

    ,Graph bootstrap percolation – a discovery of slowness, arXiv:2602.12736 (2026).Ò 1 , 1 , 1

    work page arXiv 2026

  11. [11]

    Füredi,Turán type problems

    Z. Füredi,Turán type problems. Surveys in combinatorics, 1991 (Guildford, 1991), 253–300, London Math. Soc. Lecture Note Ser166(1991).Ò 1

    1991

  12. [12]

    Gunderson, S

    K. Gunderson, S. Koch, and M. Przykucki,The time of graph bootstrap percolation, Random Structures Algorithms51(2017), no. 1, 143–168.Ò 1

    2017

  13. [13]

    Hartarsky and L

    I. Hartarsky and L. Lichev,The maximal running time of hypergraph bootstrap percolation, arXiv:2208.13489 (2022), To appear in SIAM J. Discrete Math.Ò 1

    work page arXiv 2022

  14. [14]

    Katona, T

    G. Katona, T. Nemetz, and M. Simonovits,On a problem of Turán in the theory of graphs, Mat. Lapok15(1964), 228–238.Ò 1

    1964

  15. [15]

    Keevash,Hypergraph Turán problems, Surveys in combinatorics392(2011), 83–140.Ò 1 , 2

    P. Keevash,Hypergraph Turán problems, Surveys in combinatorics392(2011), 83–140.Ò 1 , 2

    2011

  16. [16]

    W. Liu, B. Schülke, and X. Zhang,Bootstrap percolation of extension hypergraphs, arXiv:2604.04607 (2026).Ò 1

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  17. [17]

    Matzke,The saturation time of graph bootstrap percolation, arXiv:1510.06156 (2015).Ò 1

    K. Matzke,The saturation time of graph bootstrap percolation, arXiv:1510.06156 (2015).Ò 1

    work page arXiv 2015

  18. [18]

    Morris,Bootstrap percolation, and other automata, European J

    R. Morris,Bootstrap percolation, and other automata, European J. Combin.66(2017), 250–263.Ò 1 8

    2017

  19. [19]

    J. A. Noel and A. Ranganathan,On the Running Time of Hypergraph Bootstrap Percolation, arXiv:2206.02940 (2022), To appear in Electron. J. Combin.Ò 1

    work page arXiv 2022

  20. [20]

    Sidorenko,What we know and what we do not know about Turán numbers, Graphs Combin.11 (1995), no

    A. Sidorenko,What we know and what we do not know about Turán numbers, Graphs Combin.11 (1995), no. 2, 179–199.Ò 1 School of Mathematics, Shandong University, Jinan, China Email address:wcliu@sdu.edu.cn Data Science Institute, Shandong University, Jinan, China Email address:xiangxiangnie@sdu.edu.cn Institute of Computer Science of the Czech Academy of Sci...

    1995