Minimal Percolating Sets in Bootstrap Percolation

Abstract

In standard bootstrap percolation, a subset $A$ of the grid $[n]^2$ is initially infected. A new site is then infected if at least two of its neighbours are infected, and an infected site stays infected forever. The set $A$ is said to percolate if eventually the entire grid is infected. A percolating set is said to be minimal if none of its subsets percolate. Answering a question of Bollobás, we show that there exists a minimal percolating set of size $4n^2/33 + o(n^2)$, but there does not exist one larger than $(n + 2)^2/6$.