Graph bootstrap percolation -- a discovery of slowness

Read full text
Authors: David Fabian, Patrick Morris, Tibor Szabó
Cited by: 0

Abstract

Graph bootstrap percolation is a discrete-time process capturing the spread of a virus on the edges of $K_n$. Given an initial set $G\subseteq K_n$ 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 $K_n$ that is the last uninfected edge in a copy of $H$ in $K_n$ 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 influence 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.

Fields of Study & Subjects

Limits and Structures in Graph Theory Complex Network Analysis Techniques Advanced Graph Theory Research

Publication details

Journal / source
arXiv (Cornell University)
Publication date
13 February 2026
Language
EN
Document type
Preprint