Extremal Bounds for Bootstrap Percolation in the Hypercube

The r-neighbour bootstrap process on a graph G starts with an initial set A0 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 eventua...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2017-08, Vol.61, p.877-883
Main Authors: Morrison, Natasha, Noel, Jonathan A.
Format: Article
Language:English
Subjects:
Bootstrap percolation
extremal combinatorics
hypercube
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The r-neighbour bootstrap process on a graph G starts with an initial set A0 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 A0percolates. 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(drr−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.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2017.07.049