On slowly percolating sets of minimal size in bootstrap percolation

Fabricio Benevides¹ ; Michał Przykucki²

¹Universidade Federal do Ceará
²University of Cambridge

The electronic journal of combinatorics, Tome 20 (2013) no. 2

Résumé

Bootstrap percolation, one of the simplest cellular automata, can be seen as a model of the spread of infection. In $r$-neighbour bootstrap percolation on a graph $G$ we assign a state, infected or healthy, to every vertex of $G$ and then update these states in successive rounds, according to the following simple local update rule: infected vertices of $G$ remain infected forever and a healthy vertex becomes infected if it has at least $r$ already infected neighbours. We say that percolation occurs if eventually every vertex of $G$ becomes infected. A well known and celebrated fact about the classical model of $2$-neighbour bootstrap percolation on the $n \times n$ square grid is that the smallest size of an initially infected set which percolates in this process is $n$. In this paper we consider the problem of finding the maximum time a $2$-neighbour bootstrap process on $[n]^2$ with $n$ initially infected vertices can take to eventually infect the entire vertex set. Answering a question posed by Bollobás we compute the exact value for this maximum showing that, for $n \ge 4$, it is equal to the integer nearest to $(5n^2-2n)/8$.

Détail

DOI : 10.37236/2542

Classification : 05C85, 05C90, 60K35, 68Q80, 92D30
Mots-clés : bootstrap percolation, grid, maximum time