Maximum Percolation Time in Two-Dimensional Bootstrap Percolation

Abstract

We consider a classic model known as bootstrap percolation on the $n \times n$ square grid. To each vertex of the grid we assign an initial state, infected or healthy, and then in consecutive rounds we infect every healthy vertex that has at least two already infected neighbors. We say that percolation occurs if the whole grid is eventually infected. In this paper, contributing to a recent series of extremal results in this field, we prove that the maximum time a bootstrap percolation process can take to eventually infect the entire vertex set of the grid is $13n^2/18+O(n)$.