A sharper threshold for bootstrap percolation in two dimensions

DOI10.1007/S00440-010-0338-ZzbMATH Open1254.60092arXiv1002.3881OpenAlexW2087493237MaRDI QIDQ438962FDOQ438962

Robert Morris, A. E. Holroyd, Janko Gravner

Publication date: 31 July 2012

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: Two-dimensional bootstrap percolation is a cellular automaton in which sites become 'infected' by contact with two or more already infected nearest neighbors. We consider these dynamics, which can be interpreted as a monotone version of the Ising model, on an n x n square, with sites initially infected independently with probability p. The critical probability p_c is the smallest p for which the probability that the entire square is eventually infected exceeds 1/2. Holroyd determined the sharp first-order approximation: p_c sim pi^2/(18 log n) as n o infty. Here we sharpen this result, proving that the second term in the expansion is -(log n)^{-3/2+ o(1)}, and moreover determining it up to a poly(log log n)-factor. The exponent -3/2 corrects numerical predictions from the physics literature.

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

zbMATH Keywords

Ising modelbootstrap percolationcritical probability

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Metropolis dynamics relaxation via nucleation and growth
• On the behavior of some cellular automata related to bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Finite size scaling in three-dimensional bootstrap percolation
• Stretched exponential fixation in stochastic Ising models at zero temperature
• The threshold regime of finite volume bootstrap percolation.
• Metastability effects in bootstrap percolation
• Bootstrap Percolation in High Dimensions
• Exact solution of a jamming transition: Closed equations for a bootstrap percolation problem
• The sharp threshold for bootstrap percolation in all dimensions
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the hypercube
• Bootstrap percolation in three dimensions
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Majority Bootstrap Percolation on the Hypercube
• Inequalities with applications to percolation and reliability
• Integrals, partitions, and cellular automata
• The metastability threshold for modified bootstrap percolation in \(d\) dimensions
• Minimal percolating sets in bootstrap percolation
• Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation
• Slow convergence in bootstrap percolation
• Bootstrap percolation on the random regular graph
• On percolation in random graphs with given vertex degrees
• A simple model of global cascades on random networks
• Metastable behavior for bootstrap percolation on regular trees
• Local bootstrap percolation
• A nucleation-and-growth model
• On some growth models with a small parameter
• A d-dimensional nucleation and growth model
• Threshold Growth Dynamics
• Bootstrap percolation on homogeneous trees has 2 phase transitions

Cited In (44)

• Extremal bounds for bootstrap percolation in the hypercube
• Sensitive bootstrap percolation second term
• Subcritical bootstrap percolation via Toom contours
• Graph bootstrap percolation
• Characteristic exponents for two-dimensional bootstrap percolation
• The time of bootstrap percolation with dense initial sets for all thresholds
• Phase transition in the diffusion and bootstrap percolation models on regular random and Erdős-Rényi networks
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• Sharp metastability threshold for an anisotropic bootstrap percolation model
• Linear algebra and bootstrap percolation
• Higher order corrections for anisotropic bootstrap percolation
• Polluted bootstrap percolation in three dimensions
• On \(K_{2, t}\)-bootstrap percolation
• Maximal Spanning Time for Neighborhood Growth on the Hamming Plane
• Distinct parts partitions without sequences
• An Improved Upper Bound for Bootstrap Percolation in All Dimensions
• Sharp thresholds for contagious sets in random graphs
• The second term for two-neighbour bootstrap percolation in two dimensions
• The time of bootstrap percolation in two dimensions
• Refined universality for critical KCM: upper bounds
• The time of bootstrap percolation with dense initial sets
• The sharp threshold for bootstrap percolation in all dimensions
• Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness
• Subcritical \(\mathcal{U}\)-bootstrap percolation models have non-trivial phase transitions
• Bootstrap percolation on the product of the two-dimensional lattice with a Hamming square
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation
• A sharp threshold for a modified bootstrap percolation with recovery
• Lower bounds for graph bootstrap percolation via properties of polynomials
• The Application of Non-Crossing Partitions to Improving Percolation Threshold Bounds
• Percolation thresholds for robust network connectivity
• Scaling and Inverse Scaling in Anisotropic Bootstrap Percolation
• Sharp thresholds in bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Polluted bootstrap percolation with threshold two in all dimensions
• Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
• Newman-Ziff algorithm for the bootstrap percolation: application to the Archimedean lattices
• Sharp threshold for the FA-2f kinetically constrained model
• Bootstrap percolation on the Hamming torus
• Bootstrap and diffusion percolation transitions in three-dimensional lattices
• Fredrickson–Andersen model in two dimensions
• Extremal bounds for bootstrap percolation in the hypercube
• Universality for two‐dimensional critical cellular automata
• Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three

This page was built for publication: A sharper threshold for bootstrap percolation in two dimensions

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