pith. sign in

arxiv: 2604.04607 · v1 · submitted 2026-04-06 · 🧮 math.CO

Bootstrap percolation of extension hypergraphs

Weichan Liu , Bjarne Sch\"ulke , Xin Zhang This is my paper

Pith reviewed 2026-05-10 19:29 UTC · model grok-4.3

classification 🧮 math.CO
keywords bootstrap percolationhypergraphsk-graphsextension hypergraphsrunning timemaximum running time
0
0 comments X

The pith

For k-uniform hypergraphs that are extensions of fixed graphs, bootstrap percolation reaches closure in a bounded number of steps independent of n.

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

The paper shows that if F is the k-extension of any graph G on t vertices, then the longest possible bootstrap percolation process on n-vertex k-graphs using copies of F lasts at most C steps, where C depends only on k and t. This bound holds for every initial hypergraph H_0 and for all k at least 3. A reader would care because bootstrap percolation models iterative closure under local rules, and a constant-time guarantee means the process cannot produce arbitrarily long chains of dependent additions even as the vertex set grows. The result isolates the extension structure as the feature that caps the running time.

Core claim

We show that for every graph G on t vertices and every k≥3, M_{F^{(k)}(G)}(n)≤ C_{k,t} for some constant C_{k,t} depending only on t and k.

What carries the argument

The k-extension hypergraph F^{(k)}(G), formed by enlarging each edge of G with a fixed (k-2)-set of private vertices, which forces every copy of F to share vertices in a way that limits the depth of the addition sequence.

If this is right

  • The maximum running time M_F(n) remains bounded as n grows for every such extension hypergraph F.
  • The percolation process stabilizes after a fixed number of rounds for any starting hypergraph on n vertices.
  • No sequence of edge additions can be made arbitrarily long when the copies of F are structured by private vertex sets.
  • The bound applies uniformly to every base graph G with the same number of vertices t.

Where Pith is reading between the lines

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

  • The same constant-time stabilization may fail for hypergraphs F that lack the private-vertex extension structure, so the result highlights a structural condition for bounded running time.
  • Similar bounds could be sought for other families of hypergraphs whose copies are forced to overlap in fixed patterns.
  • Exact values or tighter upper bounds on C_{k,t} might be computable by enumerating the possible addition sequences for small t and k.

Load-bearing premise

The forbidden hypergraph F must be exactly the k-extension of some fixed small graph G, so that every copy uses a rigid pattern of shared and private vertices that prevents unbounded chains of additions.

What would settle it

Exhibit one fixed G on t vertices, one k≥3, and one initial k-graph H_0 on arbitrarily large n such that the F-process requires more than C_{k,t} rounds before no new edges can be added.

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)\,.$$ Recently, Noel and Ranganathan initiated the study of this quantity for $k$-graphs. In this work, we determine the asymptotics of $M_F(n)$ for a large class of $k$-graphs. Given a graph $G=(V,E)$, the $k$-extension of $G$ is a $k$-graph $F^{(k)}(G)$ obtained from $G$ by enlarging each edge with a $(k-2)$-set of new vertices. We show that for every graph $G$ on $t$ vertices and every $k\geq 3$, $M_{F^{(k)}(G)}(n)\leq C_{k,t}$ for some constant $C_{k,t}$ depending only on $t$ and $k$.

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 / 3 minor

Summary. The manuscript studies F-bootstrap percolation on k-uniform hypergraphs. For F the k-extension F^{(k)}(G) of an arbitrary graph G on t vertices (obtained by enlarging each edge of G with a private (k-2)-set), it proves that the maximum running time satisfies M_{F^{(k)}(G)}(n) ≤ C_{k,t} for a constant C_{k,t} depending only on k and t (independent of n). The result is obtained by analyzing the possible dependency chains among added k-edges under the fixed-size base structure of G.

Significance. If the proof holds, the result supplies an explicit infinite family of k-graphs on which bootstrap percolation stabilizes after a number of steps bounded independently of n. This contrasts with the potentially unbounded or n-dependent running times possible for arbitrary F and thereby enlarges the class of hypergraphs whose percolation dynamics are fully understood; it directly extends the program initiated by Noel and Ranganathan.

minor comments (3)
  1. The definition of the k-extension F^{(k)}(G) in the introduction is clear, but the precise vertex-disjointness condition on the private (k-2)-sets should be restated once more in the statement of the main theorem to avoid any ambiguity about whether the same auxiliary vertices may be reused across edges.
  2. The proof sketch in the abstract refers to 'dependency chains among added k-edges' whose length is controlled by t and k; the full argument would benefit from an explicit lemma bounding the length of such chains (e.g., a new Lemma 3.2) before the induction on the number of steps.
  3. Notation: the running-time function is denoted M_F(H_0) in the text but M_F(n) for the maximum; a single sentence reconciling the two usages at the end of Section 1 would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recognizing the significance of our result in enlarging the class of hypergraphs with n-independent running times in F-bootstrap percolation. We appreciate the recommendation for minor revision and will incorporate improvements to clarity and presentation in the revised version.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes an upper bound M_{F^{(k)}(G)}(n) ≤ C_{k,t} via direct analysis of the bootstrap percolation process on k-extension hypergraphs. The fixed vertex count t of G and the private (k-2)-sets per edge limit dependency chains to length depending only on k and t, yielding an n-independent constant without any fitted parameters, self-citations as load-bearing premises, or reductions that equate the claimed bound to its own inputs by construction. The derivation is self-contained against the definition of the F-process and the structure of F^{(k)}(G).

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard definitions of k-graphs, the F-process, and the extension construction; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of k-uniform hypergraphs and the bootstrap percolation process (adding edges that complete a copy of F) as previously defined in the literature.
    The process and objects are taken from prior work cited in the abstract.

pith-pipeline@v0.9.0 · 5603 in / 1370 out tokens · 61918 ms · 2026-05-10T19:29:07.143427+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

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.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · cited by 1 Pith paper

  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

    work page 2012

  2. [2]

    Balogh, G

    J. Balogh, G. Kronenberg, A. Pokrovskiy, and T. Szabó,The maximum length ofKr-Bootstrap Percolation, arXiv preprint arXiv:1907.04559 (2019), To appear in Proceedings of the American Mathematical Society.Ò 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

    work page 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, Electronic Journal of Combinatorics24(2017), no. 2, P2.16.Ò 1 13

    work page 2017

  5. [5]

    Chalupa, P

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

    work page 1979

  6. [6]

    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 Journal of Combinatorics.Ò 1

    work page arXiv 2022

  7. [7]

    Fabian, P

    D. Fabian, P. Morris, and T. Szabó,Slow graph bootstrap percolation I: Cycles, arXiv:2308.00498 (2023).Ò 1

    work page arXiv 2023

  8. [8]

    ,Slow graph bootstrap percolation II: Accelerating properties, Journal of Combinatorial Theory, Series B172(2025), 44–79.Ò 1 , 4

    work page 2025

  9. [9]

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

    work page arXiv 2026

  10. [10]

    Gunderson, S

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

    work page 2017

  11. [11]

    Hartarsky and L

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

    work page arXiv 2022

  12. [12]

    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

  13. [13]

    Morris,Bootstrap percolation, and other automata, European Journal of Combinatorics66(2017), 250–263.Ò 1

    R. Morris,Bootstrap percolation, and other automata, European Journal of Combinatorics66(2017), 250–263.Ò 1

    work page 2017

  14. [14]

    Mubayi,A hypergraph extension of Turán’s theorem, J

    D. Mubayi,A hypergraph extension of Turán’s theorem, J. Combin. Theory Ser. B96(2006), no. 1, 122–134.Ò 1

    work page 2006

  15. [15]

    J. A. Noel and A. Ranganathan,On the Running Time of Hypergraph Bootstrap Percolation, arXiv preprint arXiv:2206.02940 (2022), To appear in Electronic Journal of Combinatorics.Ò 1 School of Mathematics, Shandong University, Jinan, China Email address:wcliu@sdu.edu.cn Extremal Combinatorics and Probability Group, Institute for Basic Science, Daejeon, South...

    work page arXiv 2022