Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three

DOI10.1137/22M1534195MaRDI QIDQ6077983zbMATH OpenOpenAlexFDO

Authors Peter Dukes, Jonathan A. Noel

Publication date 27 September 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.07594

zbMATH Keywords

bootstrap percolationcellular automataextremal combinatoricsgridspercolationpropagation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Cellular automata (computational aspects) (68Q80) Percolation (82B43)

Abstract: For $rgeq1$, the $r$-neighbour bootstrap process in a graph $G$ starts with a set of infected vertices and, in each time step, every vertex with at least $r$ infected neighbours becomes infected. The initial infection percolates if every vertex of $G$ is eventually infected. We exactly determine the minimum cardinality of a set that percolates for the $3$-neighbour bootstrap process when $G$ is a $3$-dimensional grid with minimum side-length at least $11$. We also characterize the integers $a$ and $b$ for which there is a set of cardinality $fracab+a+b3$ that percolates for the $3$-neighbour bootstrap process in the $aimesb$ grid; this solves a problem raised by Benevides, Bermond, Lesfari and Nisse [HAL Research Report 03161419v4, 2021].

Recommendations

• Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation
• Extremal bounds for bootstrap percolation in the hypercube
• Extremal bounds for bootstrap percolation in the hypercube
• Bootstrap percolation in three dimensions

Cites work

• A sharper threshold for bootstrap percolation in two dimensions
• An improved upper bound for bootstrap percolation in all dimensions
• Bootstrap percolation in high dimensions
• Bootstrap percolation in three dimensions
• Bootstrap percolation on the hypercube
• Bootstrap percolation, probabilistic cellular automata and sharpness
• Bootstrap Percolation, the Schröder Numbers, and theN-Kings Problem
• Extremal bounds for bootstrap percolation in the hypercube
• Finite size scaling in three-dimensional bootstrap percolation
• scientific article; zbMATH DE number 5066400 (Why is no real title available?)
• Lower bounds for graph bootstrap percolation via properties of polynomials
• Majority Bootstrap Percolation on the Hypercube
• Mathematical mind-benders
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• Metastability effects in bootstrap percolation
• Monotone cellular automata in a random environment
• Polluted bootstrap percolation in three dimensions
• Proof of Straley's argument for bootstrap percolation.
• Random disease on the square grid
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Slow convergence in bootstrap percolation
• Smallest percolating sets in bootstrap percolation on grids
• Subcritical \(\mathcal{U}\)-bootstrap percolation models have non-trivial phase transitions
• The metastability threshold for modified bootstrap percolation in d dimensions
• The second term for two-neighbour bootstrap percolation in two dimensions
• The sharp threshold for bootstrap percolation in all dimensions
• The sharp threshold for the Duarte model
• The threshold regime of finite volume bootstrap percolation.

Cited in

(7)

• Polluted bootstrap percolation in three dimensions
• Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation
• Minimum 2-percolating sets in 2-connected, diameter 2 graphs
• Bootstrap percolation on the high-dimensional Hamming graph
• Spreading in claw-free cubic graphs
• 3-neighbor bootstrap percolation on grids
• On polluted bootstrap percolation in Cartesian grids

This page was built for publication: Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three

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