Minimal percolating sets in bootstrap percolation (Q1010903)

Summary: 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\).