Article ID Journal Published Year Pages File Type
8903771 Journal of Combinatorial Theory, Series A 2018 24 Pages PDF
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
, ,