Extremal Bounds for Bootstrap Percolation in the Hypercube.

The r - neighbour bootstrap process on a graph G starts with an initial set A 0 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 A 0 percolates . We prove a conjecture of Balogh and Bollobás which says that, for fixed r and large d , every percolating set in the d -dimensional hypercube has cardinality at least 1 + o ( 1 ) r ( d r r − 1 ) . We also prove an analogous result for multidimensionalrectangular grids. Our proofs exploit a connection between bootstrap percolation and a related process, known as weak saturation . In addition, we improve 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 exactly ⌈ d ( d + 3 ) 6 ⌉ + 1 for all d ≥ 3 . [ABSTRACT FROM AUTHOR]