Slow graph bootstrap percolation I: Cycles
Fabian, David; Morris, Patrick1; Szabó, Tibor2
1Universitat Politècnica de Catalunya (UPC), Departament de Matemàtiques, Carrer de Jordi Girona, 31, Barcelona, 08034 (Spain)
2Freie Universität Berlin, Institute of Mathematics, Kaiserswerther Str. 16-18, Berlin, 14195 (Germany)
Innovations in Graph Theory, Volume 3 (2026), pp. 89-126

Given a fixed graph $H$ and an $n$-vertex graph $G$, the $H$-bootstrap percolation process on $G$ is defined to be the sequence of graphs $G_i$, $i\ge 0$ which starts with $G_0 := G$ and in which $G_{i+1}$ is obtained from $G_i$ by adding every edge that completes a copy of $H$. We are interested in $M_H(n)$ which is the maximum number of steps, over all $n$-vertex graphs $G$, that this process takes to stabilise. We determine this maximum running time precisely when $H$ is a cycle, giving the first infinite family of graphs $H$ for which an exact solution is known. We find that $M_{C_k}(n)$ is of order $\log _{k-1}(n)$ for all $3\le k\in \mathbb{N}$. Interestingly though, the function exhibits different behaviour depending on the parity of $k$ and the exact location of the values of $n$ for which $M_H(n)$ increases is determined by the Frobenius number of a certain numerical semigroup depending on $k$.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.19
Classification: 05C35, 05D99, 05C38
Keywords: bootstrap percolation, running times, extremal graph theory

Fabian, David  ; Morris, Patrick  1 ; Szabó, Tibor  2

1 Universitat Politècnica de Catalunya (UPC), Departament de Matemàtiques, Carrer de Jordi Girona, 31, Barcelona, 08034 (Spain)
2 Freie Universität Berlin, Institute of Mathematics, Kaiserswerther Str. 16-18, Berlin, 14195 (Germany)
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{IGT_2026__3__89_0,
     author = {Fabian, David and Morris, Patrick and Szab\'o, Tibor},
     title = {Slow graph bootstrap percolation {I:} {Cycles}},
     journal = {Innovations in Graph Theory},
     pages = {89--126},
     year = {2026},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {3},
     doi = {10.5802/igt.19},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.19/}
}
TY  - JOUR
AU  - Fabian, David
AU  - Morris, Patrick
AU  - Szabó, Tibor
TI  - Slow graph bootstrap percolation I: Cycles
JO  - Innovations in Graph Theory
PY  - 2026
SP  - 89
EP  - 126
VL  - 3
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.19/
DO  - 10.5802/igt.19
LA  - en
ID  - IGT_2026__3__89_0
ER  - 
%0 Journal Article
%A Fabian, David
%A Morris, Patrick
%A Szabó, Tibor
%T Slow graph bootstrap percolation I: Cycles
%J Innovations in Graph Theory
%D 2026
%P 89-126
%V 3
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.19/
%R 10.5802/igt.19
%G en
%F IGT_2026__3__89_0
Fabian, David; Morris, Patrick; Szabó, Tibor. Slow graph bootstrap percolation I: Cycles. Innovations in Graph Theory, Volume 3 (2026), pp. 89-126. doi: 10.5802/igt.19

[1] Adler, Joan; Lev, Uri Bootstrap percolation: visualizations and applications, Braz. J. Phys., Volume 33 (2003), pp. 641-644 | DOI | Zbl

[2] Alfonsín, Jorge L Ramírez The Diophantine Frobenius Problem, Oxford University Press, 2005 | DOI | Zbl | MR

[3] Balogh, József; Bollobás, Béla; Morris, Robert Graph bootstrap percolation, Random Struct. Algorithms, Volume 41 (2012) no. 4, pp. 413-440 | DOI | Zbl | MR

[4] Balogh, József; Kronenberg, Gal; Pokrovskiy, Alexey; Szabó, Tibor The maximum length of K r -bootstrap percolation, Proc. Am. Math. Soc., Volume 154 (2026) no. 4, pp. 1359-1371 | Zbl | DOI | MR

[5] Behrend, Felix A. On sets of integers which contain no three terms in arithmetical progression, Proc. Natl. Acad. Sci. USA, Volume 32 (1946) no. 12, pp. 331-332 | Zbl | DOI | MR

[6] Bollobás, Béla Weakly k-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), Teubner Verlagsgesellschaft (1968), pp. 25-31 | Zbl | MR

[7] Bollobás, Béla; Przykucki, Michał; Riordan, Oliver; Sahasrabudhe, Julian On the maximum running time in graph bootstrap percolation, Electron. J. Comb., Volume 24 (2017) no. 2, Paper no. P2.16, 20 pages | DOI | Zbl | MR

[8] Chalupa, John; Leath, Paul L.; Reich, Gary R. Bootstrap percolation on a Bethe lattice, J. Phys. C. Solid State Phys., Volume 12 (1979) no. 1, Paper no. L31

[9] Espuny Díaz, Alberto; Janzer, Barnabás; Kronenberg, Gal; Lada, Joanna Long running times for hypergraph bootstrap percolation, Eur. J. Comb., Volume 115 (2024), Paper no. 103783, 18 pages | DOI | Zbl | MR

[10] Fabian, David; Morris, Patrick; Szabó, Tibor Slow graph bootstrap percolation II: Accelerating properties, J. Comb. Theory, Ser. B, Volume 172 (2025), pp. 44-79 | DOI | Zbl | MR

[11] Hartarsky, Ivailo; Lichev, Lyuben The maximal running time of hypergraph bootstrap percolation, SIAM J. Discrete Math., Volume 38 (2024) no. 2, pp. 1462-1471 | DOI | Zbl | MR

[12] Matzke, Kilian The saturation time of graph bootstrap percolation (2015) | arXiv | Zbl

[13] Morris, Robert Bootstrap percolation, and other automata, Eur. J. Comb., Volume 66 (2017), pp. 250-263 | Zbl | DOI | MR

[14] Noel, Jonathan A.; Ranganathan, Arjun On the running time of hypergraph bootstrap percolation, Electron. J. Comb., Volume 30 (2023) no. 2, Paper no. P2.46, 20 pages | DOI | Zbl | MR

[15] Przykucki, Michał Maximal percolation time in hypercubes under 2-bootstrap percolation, Electron. J. Comb., Volume 19 (2012) no. 2, Paper no. P41, 13 pages | DOI | Zbl | MR

[16] Neumann, John Theory of self-reproducing automata, University of Illinois Press, Urbana, 1966, xix+388 pages | Zbl

Cited by Sources: