On the maximum running time in graph bootstrap percolation

Béla Bollobás¹ ; Michał Przykucki² ; Oliver Riordan³ ; Julian Sahasrabudhe⁴

¹Department of Mathematics and Mathematical Statistics, Cambridge University and Department of Mathematical Sciences, University of Memphis
²Mathematical Institute, University of Oxford
³Mathematics Institute, University of Oxford
⁴Department of Mathematical Sciences, University of Memphis

The electronic journal of combinatorics, Tome 24 (2017) no. 2

Résumé

Graph bootstrap percolation is a simple cellular automaton introduced by Bollobás in 1968. Given a graph $H$ and a set $G \subseteq E(K_n)$ we initially `infect' all edges in $G$ and then, in consecutive steps, we infect every $e \in K_n$ that completes a new infected copy of $H$ in $K_n$. We say that $G$ percolates if eventually every edge in $K_n$ is infected. The extremal question about the size of the smallest percolating sets when $H = K_r$ was answered independently by Alon, Kalai and Frankl. Here we consider a different question raised more recently by Bollobás: what is the maximum time the process can run before it stabilizes? It is an easy observation that for $r=3$ this maximum is $\lceil \log_2 (n-1) \rceil $. However, a new phenomenon occurs for $r=4$ when, as we show, the maximum time of the process is $n-3$. For $r \geq 5$ the behaviour of the dynamics is even more complex, which we demonstrate by showing that the $K_r$-bootstrap process can run for at least $n^{2-\varepsilon_r}$ time steps for some $\varepsilon_r$ that tends to $0$ as $r \to \infty$.

Détail

DOI : 10.37236/5771

Classification : 05D99, 68Q80
Mots-clés : bootstrap percolation, weak saturation, cellular automata, monotone cellular automata, extremal combinatorics