The time of bootstrap percolation with dense initial sets
From MaRDI portal
Publication:400563
DOI10.1214/12-AOP818zbMATH Open1311.60113arXiv1205.3922OpenAlexW1995108421MaRDI QIDQ400563FDOQ400563
Authors: Béla Bollobás, Cecilia Holmgren, Andrew J. Uzzell, Paul Smith 
Publication date: 22 August 2014
Published in: The Annals of Probability (Search for Journal in Brave)
Abstract: In r-neighbour bootstrap percolation on the vertex set of a graph G, vertices are initially infected independently with some probability p. At each time step, the infected set expands by infecting all uninfected vertices that have at least r infected neighbours. We study the distribution of the time t at which all vertices become infected. Given t = t(n) = o(log n/log log n), we prove a sharp threshold result for the probability that percolation occurs by time t in d-neighbour bootstrap percolation on the d-dimensional discrete torus T_n^d. Moreover, we show that for certain ranges of p = p(n), the time at which percolation occurs is concentrated either on a single value or on two consecutive values. We also prove corresponding results for the modified d-neighbour rule.
Full work available at URL: https://arxiv.org/abs/1205.3922
Recommendations
Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05)
Cites Work
- Two moments suffice for Poisson approximations: The Chen-Stein method
- On the rate of Poisson convergence
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sharp metastability threshold for an anisotropic bootstrap percolation model
- Poisson approximation for dependent trials
- Largest and smallest minimal percolating sets in trees
- Title not available (Why is that?)
- Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
- On the behavior of some cellular automata related to bootstrap percolation
- Equivalence of exponential decay rates for bootstrap percolation like cellular automata
- Sharp thresholds in bootstrap percolation
- Sharp metastability threshold for two-dimensional bootstrap percolation
- Metastability effects in bootstrap percolation
- On slowly percolating sets of minimal size in bootstrap percolation
- A sharper threshold for bootstrap percolation in two dimensions
- The sharp threshold for bootstrap percolation in all dimensions
- Title not available (Why is that?)
- Bootstrap percolation on the random graph \(G_{n,p}\)
- Bootstrap percolation on the hypercube
- Bootstrap percolation in three dimensions
- Compound Poisson approximation for nonnegative random variables via Stein's method
- Poisson approximation for some statistics based on exchangeable trials
- Critical length for semi-oriented bootstrap percolation
- Proof of Straley's argument for bootstrap percolation.
- Finite-size effects for anisotropic bootstrap percolation: Logarithmic corrections
- Integrals, partitions, and cellular automata
- The metastability threshold for modified bootstrap percolation in \(d\) dimensions
- The Erdős-Rényi law in distribution, for coin tossing and sequence matching
- Random disease on the square grid
- Minimal percolating sets in bootstrap percolation
- Rates for the probability of large cubes being non-internally spanned in modified bootstrap percolation
- Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation
- Maximal percolation time in hypercubes under 2-bootstrap percolation
- Convolution bootstrap percolation models, Markov-type stochastic processes, and mock theta functions
- Characteristic exponents for two-dimensional bootstrap percolation
- Slow convergence in bootstrap percolation
Cited In (12)
- Sensitive bootstrap percolation second term
- The time of bootstrap percolation with dense initial sets for all thresholds
- Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
- The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
- The time of bootstrap percolation in two dimensions
- On slowly percolating sets of minimal size in bootstrap percolation
- Contagious sets in dense graphs
- Bootstrap Percolation on Degenerate Graphs
- Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
- Approximating dependent rare events
- The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
- The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
This page was built for publication: The time of bootstrap percolation with dense initial sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q400563)
