
Fabricio Benevides

Michał Przykucki
Keywords:
Bootstrap percolation, grid, maximum time
Abstract
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^22n)/8$.