The Library
Extremal bounds for bootstrap percolation in the hypercube
Tools
Tools
Tools
Morrison, Natasha and Noel, Jonathan A. (2018) Extremal bounds for bootstrap percolation in the hypercube. Journal of Combinatorial Theory, Series A, 156 . pp. 61-84. doi:10.1016/j.jcta.2017.11.018 ISSN 0097-3165.
|
PDF
WRAP-extremal-bounds-bootstrap-percolation-hypercube-Noel-2018.pdf - Accepted Version - Requires a PDF viewer. Download (686Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.jcta.2017.11.018
Abstract
The r-neighbour bootstrap percolation 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 A0 percolates.
We prove a conjecture of Balogh and Bollob ́as which says that, for fixed r and d →∞ , 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 ⌈ d (d +3) / 6 ⌉ + 1 for all d ≥ 3.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| Library of Congress Subject Headings (LCSH): | Hypercube, Bootstrap (Statistics), Combinatorial analysis | ||||||||
| Journal or Publication Title: | Journal of Combinatorial Theory, Series A | ||||||||
| Publisher: | Elsevier BV | ||||||||
| ISSN: | 0097-3165 | ||||||||
| Official Date: | May 2018 | ||||||||
| Dates: |
|
||||||||
| Volume: | 156 | ||||||||
| Page Range: | pp. 61-84 | ||||||||
| DOI: | 10.1016/j.jcta.2017.11.018 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 5 July 2018 | ||||||||
| Date of first compliant Open Access: | 28 December 2018 | ||||||||
| RIOXX Funder/Project Grant: |
|
||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
