Extremal bounds for bootstrap percolation in the hypercube

We prove a conjecture of Balogh and Bollobás which says that, for fixed r and d→∞, every percolating set in the d-dimensional hypercube has cardinality at least 1+o(1)r(dr−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.