Extremal bounds for bootstrap percolation in the hypercube

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:156

Article

Morrison, Natasha^1,4  Noel, Jonathan A.^2,3,4 

[1] Univ Cambridge, Dept Pure Math & Math Stat, Wilberforce Rd, Cambridge CB3 0WB, England

[2] Univ Warwick, Dept Comp Sci, Coventry CV4 7AL, W Midlands, England

[3] Univ Warwick, DIMAP, Coventry CV4 7AL, W Midlands, England

[4] Univ Oxford, Oxford, England

关键词: Bootstrap percolation;    Hypercube;    Extremal combinatorics;    Linear algebra;    Weak saturation;   

DOI  :  10.1016/j.jcta.2017.11.018

来源: Elsevier

【 摘 要 】

The r-neighbour bootstrap percolation 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 Bollobas which says that, for fixed r and d -> infinity, 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 inverted right perpendicular d(d+3)/6 inverted left perpendicular + for all d >= 3. (C) 2017 Elsevier Inc. All rights reserved.

【 授权许可】

Free