The time of bootstrap percolation with dense initial sets
Authors:
- Béla BollobásBBBéla Bollobás
- Cecilia HolmgrenCHCecilia Holmgren
- Paul SmithPSPaul Smith
- Andrew J. UzzellAUAndrew J. Uzzell
Open Access
- 1 July 2014
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Probability
- Vol. 42 (4) , 1337-1373
Abstract
Let $r\in\mathbb{N}$. 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. When $p$ is close to 1, we study the distribution of the time 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 $\mathbb{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.
Keywords
This publication has 35 references indexed in Scilit:
- Bootstrap percolation on the random graph $G_{n,p}$The Annals of Applied Probability, 2012
- Convolution Bootstrap Percolation Models, Markov-type Stochastic Processes, and Mock Theta FunctionsInternational Mathematics Research Notices, 2012
- A sharper threshold for bootstrap percolation in two dimensionsProbability Theory and Related Fields, 2010
- Bootstrap percolation in three dimensionsThe Annals of Probability, 2009
- Sharp metastability threshold for two-dimensional bootstrap percolationProbability Theory and Related Fields, 2003
- Characteristic Exponents for Two-Dimensional Bootstrap PercolationThe Annals of Probability, 1993
- Rates for the probability of large cubes being non-internally spanned in modified bootstrap percolationProbability Theory and Related Fields, 1992
- Two Moments Suffice for Poisson Approximations: The Chen-Stein MethodThe Annals of Probability, 1989
- Proof of Straley's argument for bootstrap percolationJournal of Statistical Physics, 1987
- Poisson approximation for some statistics based on exchangeable trialsAdvances in Applied Probability, 1983