Graph bootstrap percolation

Abstract

Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollobás in 1968, and is defined as follows. Given a graph $H$, and a set $G\subset E(K_n)$ of initially `infected' edges, we infect, at each time step, a new edge $e$ if there is a copy of $H$ in $K_n$ such that $e$ is the only not-yet infected edge of $H$. We say that $G$ percolates in the $H$-bootstrap process if eventually every edge of $K_n$ is infected. The extremal questions for this model, when $H$ is the complete graph $K_r$, were solved (independently) by Alon, Kalai and Frankl almost thirty years ago. In this paper we study the random questions, and determine the critical probability $p_c(n,K_r)$ for the $K_r$-process up to a poly-logarithmic factor. In the case $r=4$ we prove a stronger result, and determine the threshold for $p_c(n,K_4)$.

27 pages

Cited by in corpus (2)

• Bootstrap percolation on the random graph $G_{n,p}$
• NP-Completeness Results for Graph Burning on Geometric Graphs