Smallest percolating sets in bootstrap percolation on grids

Abstract

In this paper we fill in a fundamental gap in the extremal bootstrap percolation literature, by providing the first proof of the fact that for all $d\ge 1$, the size of the smallest percolating sets in $d$-neighbour bootstrap percolation on $[n{]}^d$, the $d$-dimensional grid of size $n$, is $n^{d-1}$. Additionally, we prove that such sets percolate in time at most $c_d{n}^2$, for some constant $c_d>0$ depending on $d$ only.

11 pages, 3 figures