On slowly percolating sets of minimal size in bootstrap percolation (Q396751)

Summary: 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 \geq 4\), it is equal to the integer nearest to \((5n^2-2n)/8\).