Book contents
- Frontmatter
- Contents
- Preface
- Phase Transitions in Random Planar Graphs
- Extremal Poset Theory
- Techniques for Taming Temporal Graphs
- Asymptotic Enumeration via Graph Containers and Entropy
- Graph Bootstrap Percolation – A Discovery of Slowness
- Rigidity of Graphs and Frameworks: A Matroid Theoretic Approach
- Monadic Second-Order Logic for Hypergraphs and Matroids
- Domino Tilings Beyond 2D
- References
Graph Bootstrap Percolation – A Discovery of Slowness
Published online by Cambridge University Press: 06 June 2026
Book contents
- Frontmatter
- Contents
- Preface
- Phase Transitions in Random Planar Graphs
- Extremal Poset Theory
- Techniques for Taming Temporal Graphs
- Asymptotic Enumeration via Graph Containers and Entropy
- Graph Bootstrap Percolation – A Discovery of Slowness
- Rigidity of Graphs and Frameworks: A Matroid Theoretic Approach
- Monadic Second-Order Logic for Hypergraphs and Matroids
- Domino Tilings Beyond 2D
- References
Summary
Graph bootstrap percolation is a discrete-time process capturing the spread of a virus on the edges of Kn. Given an initial set G ⊆ Kn of infected edges, the transmission of the virus is governed by a fixed graph H: in each round of the process, any edge e of Kn that is the last uninfected edge in a copy of H in Kn gets infected as well. Once infected, edges remain infected forever. The process was introduced by Bollobás in 1968 in the context of weak saturation and has since inspired a vast array of beautiful mathematics. The main focus of this survey is the extremal question of how long the infection process can last before stabilising. We give an exposition of our recent systematic study of this maximum running time and the inuence of the infection rule H. The topic turns out to possess a wide variety of interesting behaviour, with connections to additive, extremal, and probabilistic combinatorics. Along the way, we encounter a number of surprises and attractive open problems.
Information
- Type
- Chapter
- Information
- Surveys in Combinatorics 2026 , pp. 141 - 188Publisher: Cambridge University PressPrint publication year: 2026
References
Adler, J. and Lev, U., Bootstrap percolation: visualizations and applications, Brazilian Journal of Physics 33 (2003), 641–644.10.1590/S0103-97332003000300031CrossRefGoogle Scholar
Adler, J., Stauffer, D., and Aharony, A., Comparison of bootstrap percolation models, Journal of Physics A: Mathematical and General 22 (1989), no. 7, L297–L301.10.1088/0305-4470/22/7/008CrossRefGoogle Scholar
Aizenman, M. and Lebowitz, J. L., Metastability effects in bootstrap percolation, Journal of Physics A: Mathematical and General 21 (1988), no. 19, 3801.10.1088/0305-4470/21/19/017CrossRefGoogle Scholar
Akhmejanova, M., Vorobyev, I., and Zhukovskii, M., Weak saturation numbers of large complete bipartite graphs, arXiv preprint arXiv:2508.19435 (2025).Google Scholar
Alon, N., An extremal problem for sets with applications to graph theory, Journal of Combinatorial Theory, Series A 40 (1985), no. 1, 82–89.10.1016/0097-3165(85)90048-2CrossRefGoogle Scholar
Angel, O. and Kolesnik, B., Sharp thresholds for contagious sets in random graphs, The Annals of Applied Probability 28 (2018), no. 2, 1052–1098.Google Scholar
Ascoli, R. and He, X., Rational values of the weak saturation limit, arXiv preprint arXiv:2501.15686 (2025).Google Scholar
Balister, P., Bollobás, B., and Smith, P., The time of bootstrap percolation in two dimensions, Probability Theory and Related Fields 166 (2016), no. 1-2, 321–364.Google Scholar
Balogh, J. and Bollobás, B., Bootstrap percolation on the hypercube, Probability Theory and Related Fields 134 (2006), no. 4, 624–648.Google Scholar
Balogh, J., Bollobás, B., and Morris, R., Bootstrap percolation in three dimensions, The Annals of Probability (2009), 1329–1380.Google Scholar
Balogh, J., Bollobás, B., and Morris, R., Majority bootstrap percolation on the hypercube, Combinatorics, Probability and Computing 18 (2009), no. 1-2, 17–51.Google Scholar
Balogh, J., Bollobás, B., and Morris, R., Bootstrap percolation in high dimensions, Combinatorics, Probability and Computing 19 (2010), no. 5-6, 643–692.Google Scholar
Balogh, J., Bollobás, B., and Morris, R., Graph bootstrap percolation, Random Structures & Algorithms 41 (2012), no. 4, 413–440.Google Scholar
Balogh, J., Kronenberg, G., Pokrovskiy, A., and Szabó, T., The maximum length of Kr-Bootstrap Percolation, arXiv preprint arXiv:1907.04559 (2019), To appear in Proceedings of the American Mathematical Society.Google Scholar
Bartha, Z. and Kolesnik, B., Weakly saturated random graphs, Random Structures & Algorithms 65 (2024), no. 1, 131–148.Google Scholar
Bartha, Z., Kolesnik, B., and Kronenberg, G., H-percolation with a random H, Electronic Communications in Probability 29 (2024), 1–5.10.1214/24-ECP602CrossRefGoogle Scholar
Bartha, Z., Kolesnik, B., Kronenberg, G., and Peled, Y., Sharp Fuss-Catalan thresholds in graph bootstrap percolation, arXiv preprint arXiv:2510.26724 (2025).Google Scholar
Bayraktar, E. and Chakraborty, S., Kr,s graph bootstrap percolation, Preprint (2019), arXiv:1904.12764.Google Scholar
Behrend, F. A., On sets of integers which contain no three terms in arithmetical progression, Proceedings of the National Academy of Sciences of the United States of America 32 (1946), no. 12, 331.10.1073/pnas.32.12.331CrossRefGoogle ScholarPubMed
Benevides, F. and Przykucki, M., On slowly percolating sets of minimal size in bootstrap percolation, Electronic Journal of Combinatorics 20 (2013), no. 2, P46.CrossRefGoogle Scholar
Benevides, F. and Przykucki, M., Maximum percolation time in two-dimensional bootstrap percolation, SIAM Journal on Discrete Mathematics 29 (2015), no. 1, 224–251.Google Scholar
Bidgoli, M., Mohammadian, A., and Tayfeh-Rezaie, B., On K2,t-Bootstrap Percolation, Graphs and Combinatorics 37 (2021), no. 3, 731–741.Google Scholar
Biskup, M. and Schonmann, R., Metastable behavior for bootstrap percolation on regular trees, Journal of Statistical Physics 136 (2009), no. 4, 667–676.10.1007/s10955-009-9798-xCrossRefGoogle Scholar
Bollobás, B., Weakly k-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), 1968, pp. 25–31.Google Scholar
Bollobás, B., Holmgren, C., Smith, P., and Uzzell, A., The time of bootstrap percolation with dense initial sets, Annals of Probability 42 (2014), no. 4, 1337–1373.Google Scholar
Bollobás, B., Przykucki, M., Riordan, O., and Sahasrabudhe, J., On the maximum running time in graph bootstrap percolation, Electronic Journal of Combinatorics 24 (2017), no. 2, P2.16.10.37236/5771CrossRefGoogle Scholar
Bollobás, B., Smith, P., and Uzzell, A. J., The time of bootstrap percolation with dense initial sets for all thresholds, Random Structures & Algorithms 47 (2015), no. 1, 1–29.Google Scholar
Bollobás, B. and Thomason, A. G., Threshold functions, Combinatorica 7 (1987), no. 1, 35–38.Google Scholar
Borowiecki, M. and Sidorowicz, E., Weakly p-saturated graphs, Discussiones Mathematicae Graph Theory 22 (2002), no. 1, 17–29.Google Scholar
Cancrini, N., Martinelli, F., Roberto, C., and Toninelli, C., Kinetically constrained spin models, Probability theory and related fields 140 (2008), no. 3, 459–504.Google Scholar
Cerf, R. and Manzo, F., The threshold regime of finite volume bootstrap percolation, Stochastic Processes and their Applications 101 (2002), no. 1, 69–82.Google Scholar
Chalupa, J., Leath, P. L., and Reich, G. R., Bootstrap percolation on a Bethe lattice, Journal of Physics C: Solid State Physics 12 (1979), no. 1, L31.10.1088/0022-3719/12/1/008CrossRefGoogle Scholar
Chen, W., Liu, X., and Yang, X., A note on weak saturation number of trees, arXiv preprint arXiv:2502.15626 (2025).Google Scholar
Cui, Y. and Pu, L., Weak saturation numbers of K2,t and Kp ∪ Kq, AKCE International Journal of Graphs and Combinatorics 16 (2019), no. 3, 237–240.10.1016/j.akcej.2019.04.003CrossRefGoogle Scholar
Currie, B. L., Faudree, J. R., Faudree, R. J., and Schmitt, J. R., A survey of minimum saturated graphs, Electronic Journal of Combinatorics (2012), DS19–Oct 11, 2021.Google Scholar
Dukes, P., Noel, J., and Romer, A., Extremal bounds for 3-neighbor bootstrap percolation in dimensions two and three, SIAM Journal on Discrete Mathematics 37 (2023), no. 3, 2088–2125.Google Scholar
Erdős, P., Some recent results on extremal problems in graph theory, Theory of Graphs (Rome, 1966), Gordon and Breach, New York, 1967, pp. 117–123.Google Scholar
Erdős, P., Füredi, Z., and Tuza, Z., Saturated r-uniform hypergraphs, Discrete mathematics 98 (1991), no. 2, 95–104.Google Scholar
Erdős, P., Hajnal, A., and Moon, J., A problem in graph theory, The American Mathematical Monthly 71 (1964), no. 10, 1107–1110.Google Scholar
Erdős, P. and Simonovits, M., Some extremal problems in graph theory, Combinatorial Theory and its Applications I, North-Holland Amsterdam, 1970, pp. 378–392.Google Scholar
Espuny Díaz, A., Janzer, B., Kronenberg, G., and Lada, J., Long running time for hypergraph bootstrap percolation, European Journal of Combinatorics 115 (2024), 103783.10.1016/j.ejc.2023.103783CrossRefGoogle Scholar
Fabian, D., Morris, P., and Szabó, T., Slow graph bootstrap percolation I: Cycles, arXiv preprint arXiv:2308.00498 (2023).Google Scholar
Fabian, D., Morris, P., and Szabó, T., Slow graph bootstrap percolation II: Accelerating properties, Journal of Combinatorial Theory, Series B 172 (2025), 44–79.10.1016/j.jctb.2024.12.006CrossRefGoogle Scholar
Fabian, D., Morris, P., and Szabó, T., Slow graph bootstrap percolation III: Chain constructions, arXiv preprint arXiv:2508.03835 (2025).Google Scholar
Faudree, R. J., Gould, R. J., and Jacobson, M. S., Weak saturation numbers for sparse graphs, Discussiones Mathematicae Graph Theory 33 (2013), no. 4, 677–693.Google Scholar
Frankl, P., An extremal problem for two families of sets, European Journal of Combinatorics 3 (1982), no. 2, 125–127.10.1016/S0195-6698(82)80025-5CrossRefGoogle Scholar
Füredi, Z. and Simonovits, M., The history of degenerate (bipartite) extremal graph problems, Erdős Centennial, Springer, 2013, pp. 169–264.10.1007/978-3-642-39286-3_7CrossRefGoogle Scholar
Gunderson, K., Koch, S., and Przykucki, M., The time of graph bootstrap percolation, Random Structures & Algorithms 51 (2017), no. 1, 143–168.Google Scholar
Hartarsky, I. and Lichev, L., The maximal running time of hypergraph bootstrap percolation, SIAM Journal on Discrete Mathematics 38 (2024), no. 2, 1462–1471.Google Scholar
Holroyd, A. E., Sharp metastability threshold for two-dimensional bootstrap percolation, Probability Theory and Related Fields 125 (2003), no. 2, 195–224.Google Scholar
Janson, S., Łuczak, T., Turova, T., and Vallier, T., Bootstrap percolation on the random graph Gn,p, The Annals of Applied Probability 22 (2012), no. 5, 1989–2047.Google Scholar
Kalai, G., Weakly saturated graphs are rigid, Convexity and graph theory, North-Holland Mathematics Studies, vol. 87, 1984, pp. 189–190.Google Scholar
Kalai, G., Hyperconnectivity of graphs, Graphs and Combinatorics 1 (1985), no. 1, 65–79.Google Scholar
Kővári, P., Sós, V. T., and Turán, P., On a problem of Zarankiewicz, Colloquium Mathematicum, vol. 3, Polska Akademia Nauk, 1954, pp. 50–57.10.4064/cm-3-1-50-57CrossRefGoogle Scholar
Kim, J. H., Sudakov, B., and Vu, V. H., On the asymmetry of random regular graphs and random graphs, Random Structures & Algorithms 21 (2002), no. 3-4, 216–224.Google Scholar
Kolesnik, B., The sharp K4-percolation threshold on the Erdős–Rényi random graph, Electronic Journal of Probability 27 (2022), 1–23.CrossRefGoogle Scholar
Korándi, D., Peled, Y., and Sudakov, B., A random triadic process, SIAM Journal on Discrete Mathematics 30 (2016), no. 1, 1–19.Google Scholar
Kronenberg, G., Martins, T., and Morrison, N., Weak saturation numbers of complete bipartite graphs in the clique, Journal of Combinatorial Theory, Series A 178 (2021).Google Scholar
Lazebnik, F., Ustimenko, V. A., and Woldar, A. J., A new series of dense graphs of high girth, Bulletin of the American Mathematical Society 32 (1995), no. 1, 73–79.Google Scholar
Lazebnik, F. and Viglione, R., On the connectivity of certain graphs of high girth, Discrete Mathematics 277 (2004), no. 1-3, 309–319.Google Scholar
Lovász, L., Flats in matroids and geometric graphs, Combinatorial Surveys (Proc. 6th British Combinatorial Conference), 1977, pp. 45–86.Google Scholar
Matzke, K., The saturation time of graph bootstrap percolation, arXiv preprint arXiv:1510.06156 (2015).Google Scholar
Morris, R., Bootstrap percolation, and other automata, European Journal of Combinatorics 66 (2017), 250–263.10.1016/j.ejc.2017.06.024CrossRefGoogle Scholar
Morris, R., Monotone cellular automata, Surveys in Combinatorics 2017, London Mathematical Society Lecture Note Series, Cambridge University Press, 2017, pp. 312–371.Google Scholar
Morrison, N. and Noel, J. A., Extremal bounds for bootstrap percolation in the hypercube, Journal of Combinatorial Theory, Series A 156 (2018), 61–84.10.1016/j.jcta.2017.11.018CrossRefGoogle Scholar
Morrison, N. and Noel, J. A., A sharp threshold for bootstrap percolation in a random hypergraph, Electronic Journal of Probability 26 (2021), 1–85.10.1214/21-EJP650CrossRefGoogle Scholar
Noel, J. A. and Ranganathan, A., On the Running Time of Hypergraph Bootstrap Percolation, Electronic Journal of Combinatorics 30 (2023), no. 2, P2.46.CrossRefGoogle Scholar
Pikhurko, O., Uniform families and count matroids, Graphs and Combinatorics 17 (2001), no. 4, 729–740.Google Scholar
Pikhurko, O., Weakly saturated hypergraphs and exterior algebra, Combinatorics, Probability and Computing 10 (2001), no. 5, 435–451.Google Scholar
Przykucki, M., Maximal percolation time in hypercubes under 2-bootstrap percolation, Electronic Journal of Combinatorics 19 (2012), no. 2, P41.10.37236/2412CrossRefGoogle Scholar
Przykucki, M. and Shelton, T., Smallest percolating sets in bootstrap percolation on grids, arXiv preprint arXiv:1907.01940 (2019).Google Scholar
Roth, K. F., On certain sets of integers, J. London Math. Soc 28 (1953), no. 1, 104–109.Google Scholar
Ruzsa, I., Solving a linear equation in a set of integers I, Acta Arithmetica 65 (1993), no. 3, 259–282 (en).Google Scholar
Ruzsa, I. and Szemerédi, E., Triple systems with no six points carrying three triangles, Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18 (1978), no. 939-945, 2.Google Scholar
A. Shapira, Behrend-type constructions for sets of linear equations, Acta Arithmetica 122 (2006), no. 1, 17–33.Google Scholar
Terekhov, N. and Zhukovskii, M., Weak saturation in graphs: a combinatorial approach, Journal of Combinatorial Theory, Series B 172 (2025), 146–167.10.1016/j.jctb.2024.12.007CrossRefGoogle Scholar
Tuza, Z., Extremal problems on saturated graphs and hypergraphs, Ars Combinatorica, Eleventh British Combinatorial Conference (London 1987) 25b (1988), 105–113.Google Scholar
Ulam, S., Random processes and transformations, Proceedings of the International Congress on Mathematics 1950, 1952, pp. 264–275.Google Scholar
von Neumann, J., Theory of self-reproducing automata, University of Illinois Press, Urbana, 1966.Google Scholar
Accessibility standard: WCAG 2.2 A
Why this information is here
This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.Accessibility Information
The PDF of this chapter complies with version 2.2 of the
Web Content Accessibility Guidelines
(WCAG), offering more comprehensive accessibility measures for a broad range
of users and meets the basic
(A)
level of WCAG compliance, addressing essential accessibility barriers.
Content Navigation
Table of contents navigation
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Index navigation
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Reading Order & Textual Equivalents
Single logical reading order
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
Short alternative textual descriptions
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.