3-Bootstrap Percolation on Grids and Tori

Title: 3-Bootstrap Percolation on Grids and Tori

Abstract:
At each step of the k-neighbor bootstrap percolation process on a graph, every uninfected vertex with at least k infected neighbors becomes infected. An initial set of infected vertices PERCOLATES if eventually every vertex becomes infected. Determining the minimum size of a percolating set under the 2-bootstrap model is a classic combinatorial puzzle -- the slower infection of the 3-bootstrap process seems harder to analyze.  Building on the work of Dukes, Noel, and Romer, we determine precisely the minimum size of a percolating in an (m x n) grid. We then consider the same question for toroidal grid graphs.