Slow convergence in bootstrap percolation

DOI10.1214/07-AAP473zbMATH Open1141.60062arXiv0705.1347MaRDI QIDQ930671FDOQ930671

A. E. Holroyd, Janko Gravner

Publication date: 1 July 2008

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: In the bootstrap percolation model, sites in an L by L square are initially infected independently with probability p. At subsequent steps, a healthy site becomes infected if it has at least 2 infected neighbours. As (L,p)->(infinity,0), the probability that the entire square is eventually infected is known to undergo a phase transition in the parameter p log L, occurring asymptotically at lambda = pi^2/18. We prove that the discrepancy between the critical parameter and its limit lambda is at least Omega((log L)^(-1/2)). In contrast, the critical window has width only Theta((log L)^(-1)). For the so-called modified model, we prove rigorous explicit bounds which imply for example that the relative discrepancy is at least 1% even when L = 10^3000. Our results shed some light on the observed differences between simulations and rigorous asymptotics.

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

Recommendations

• Sharp metastability threshold for two-dimensional bootstrap percolation
• A sharper threshold for bootstrap percolation in two dimensions
• A sharp threshold for a modified bootstrap percolation with recovery
• The second term for two-neighbour bootstrap percolation in two dimensions
• Bootstrap percolation in high dimensions

zbMATH Keywords

crossovercellular automatonmetastabilitybootstrap percolationfinite-size scaling

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Percolation (82B43)

Cites Work

• Percolation
• Component behavior near the critical point of the random graph process
• Every monotone graph property has a sharp threshold
• Sharp thresholds in bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Stretched exponential fixation in stochastic Ising models at zero temperature
• Metastability effects in bootstrap percolation
• Exact solution of a jamming transition: Closed equations for a bootstrap percolation problem
• Kinetically constrained spin models
• Proof of Straley's argument for bootstrap percolation.
• Integrals, partitions, and cellular automata
• The metastability threshold for modified bootstrap percolation in \(d\) dimensions
• Partitions with short sequences and mock theta functions
• Integrals, partitions and MacMahon's theorem
• Phase transition and finite-size scaling for the integer partitioning problem

Cited In (22)

• Sensitive bootstrap percolation second term
• \(\mathcal{U}\)-bootstrap percolation: critical probability, exponential decay and applications
• Higher order corrections for anisotropic bootstrap percolation
• Refined universality for critical KCM: lower bounds
• A PROOF OF ANDREWS’ CONJECTURE ON PARTITIONS WITH NO SHORT SEQUENCES
• An Improved Upper Bound for Bootstrap Percolation in All Dimensions
• On the running time of hypergraph bootstrap percolation
• The second term for two-neighbour bootstrap percolation in two dimensions
• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• The time of bootstrap percolation with dense initial sets
• The sharp threshold for bootstrap percolation in all dimensions
• A sharper threshold for bootstrap percolation in two dimensions
• Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness
• Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• Scaling and Inverse Scaling in Anisotropic Bootstrap Percolation
• Sharp threshold for the FA-2f kinetically constrained model
• Title not available (Why is that?)
• Compatible Sequences and a Slow Winkler Percolation
• Recent advances in percolation theory and its applications
• Fredrickson–Andersen model in two dimensions
• Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three

This page was built for publication: Slow convergence in bootstrap percolation

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