Extremal bounds for bootstrap percolation in the hypercube

The r-neighbour bootstrap percolation process on a graph G starts with an initial set A0 of “infected” vertices and, at each step of the process, a healthy vertex becomes infected if it has at least r infected neighbours (once a vertex becomes infected, it remains infected forever). If every vertex of G eventually becomes infected, then we say that A0 percolates. We prove a conjecture of Balogh and Bollob ́as which says that, for fixed r and d →∞ , every percolating set in the d -dimensional hypercube has cardinality at least 1+ o (1) / r ( d r − 1 ). We also prove an analogous result for multidimensional rectangular grids. Our proofs exploit a connection between bootstrap percolation and a related process, known as weak saturation. In addition, we improve on the best known upper bound for the minimum size of a percolating set in the hypercube. In particular, when r = 3, we prove that the minimum cardinality of a percolating set in the d -dimensional hypercube is ⌈ d (d +3) / 6 ⌉ + 1 for all d ≥ 3