Minimal percolating sets in bootstrap percolation
Abstract
Description
In standard bootstrap percolation, a subset A of the n x n grid 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 Bollobas, 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.
19 pgs, 4 figures, thorough rewrite, to appear in Electronic J. Combinatorics
19 pgs, 4 figures, thorough rewrite, to appear in Electronic J. Combinatorics