Extremal bounds for bootstrap percolation in the hypercube

DOI10.1016/J.ENDM.2017.07.049MaRDI QIDQ5915829zbMATH OpenOpenAlexFDO

Authors Natasha Morrison, Jonathan A. Noel

Publication date 18 January 2018

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.04686, http://wrap.warwick.ac.uk/103914/1/WRAP-extremal-bounds-bootstrap-percolation-hypercube-Noel-2018.pdf

zbMATH Keywords

bootstrap percolationextremal combinatoricshypercube

Mathematics Subject Classification ID

Extremal set theory (05D05) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: 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 Bollob'as which says that, for fixed $r$ and $doinfty$, every percolating set in the $d$-dimensional hypercube has cardinality at least $$. 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 $leftlceilfracd(d+3)6ightceil+1$ for all $dgeq3$.

Recommendations

• Extremal bounds for bootstrap percolation in the hypercube
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Bootstrap percolation in high dimensions
• The sharp threshold for bootstrap percolation in all dimensions
• Bootstrap percolation on the hypercube

Cites work

• A sharper threshold for bootstrap percolation in two dimensions
• An extremal problem for sets with applications to graph theory
• Bootstrap percolation in high dimensions
• Bootstrap percolation in three dimensions
• Bootstrap percolation on the hypercube
• Exact bounds for some hypergraph saturation problems
• Finite size scaling in three-dimensional bootstrap percolation
• scientific article; zbMATH DE number 3920492 (Why is no real title available?)
• scientific article; zbMATH DE number 3275275 (Why is no real title available?)
• Hyperconnectivity of graphs
• Linear algebra and bootstrap percolation
• Majority Bootstrap Percolation on the Hypercube
• Metastability effects in bootstrap percolation
• On a packing and covering problem
• Saturation in the hypercube and bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• The sharp threshold for bootstrap percolation in all dimensions
• The threshold regime of finite volume bootstrap percolation.
• Weakly saturated hypergraphs and exterior algebra
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)

Cited in

(18)

• Minimal percolating sets in bootstrap percolation
• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• Neighborhood growth dynamics on the Hamming plane
• A cube dismantling problem related to bootstrap percolation
• Lower bounds for graph bootstrap percolation via properties of polynomials
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Anisotropic bootstrap percolation in three dimensions
• Smallest percolating sets in bootstrap percolation on grids
• Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
• Maximal induced paths and minimal percolating sets in hypercubes
• Majority Bootstrap Percolation on the Hypercube
• An improved upper bound for bootstrap percolation in all dimensions
• On the maximum running time in graph bootstrap percolation
• Saturation in the hypercube and bootstrap percolation
• Extremal bounds for bootstrap percolation in the hypercube
• Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three
• Bootstrap percolation on the hypercube
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation

This page was built for publication: Extremal bounds for bootstrap percolation in the hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5915829)