Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903771 | Journal of Combinatorial Theory, Series A | 2018 | 24 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Natasha Morrison, Jonathan A. Noel,