The critical activation density in graph bootstrap percolation

Abstract

In graph bootstrap percolation, edges of an Erdős-Rényi random graph ${\mathcal{G}}_{n,p}$ are initially active, and activation spreads to other edges of $K_n$ via the combinatorics of a fixed graph $H$: an edge becomes active whenever it is the unique inactive edge in a copy of $H$. The process $H$-percolates if all edges of $K_n$ are eventually activated. While classical cases such as $H=K_3$ (connectivity) and $H=K_4$ (related to $2$-neighbor bootstrap percolation) have been studied extensively, general graphs $H$ can exhibit wildly different behaviors. In this work, we determine the critical $H$-percolation threshold $p_c(n,H)$ for every graph $H$, fully resolving a longstanding open question of Balogh, Bollobás, and Morris. The location of $p_c(n,H)$ is governed by a new, universal parameter $\rho (H)$, which measures the maximal efficiency of witness graphs that activate an edge. To achieve this, we introduce a novel framework based on the unfolding and refolding of witness graphs. While previous works were restricted to specific families of $H$, our approach provides a unified strategy for all $H$. Inspired by algebraic topology, we lift witness graphs to covering graphs and algorithmically embed folded versions into ${\mathcal{G}}_{n,p}$ via a sequence of extensions. Crucially, this allows us to incorporate highly efficient witness graphs of unbounded size, which are potentially far larger than ${\mathcal{G}}_{n,p}$ itself. Beyond resolving $p_c(n,H)$, our framework recovers and strengthens several existing bounds in the literature. Finally, we initiate the study of the universal density parameter $\rho (H)$ and pose central open questions regarding its computability and its exact correspondence with the sharpness of the $H$-percolation threshold.

v2: revised abstract, otherwise unchanged