THE TIME OF BOOTSTRAP PERCOLATION WITH DENSE INITIAL SETS

Let r ϵ ℕ. 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 s...

Full description

Saved in:
Bibliographic Details
Published in:The Annals of probability 2014-07, Vol.42 (4), p.1337-1373
Main Authors: Bollobás, Béla, Holmgren, Cecilia, Smith, Paul, Uzzell, Andrew J.
Format: Article
Language:English
Subjects:
60C05
60K35
Approximation
Bootstrap method
Bootstrap percolation
Cellular automata
Coordinate systems
Dimensional analysis
Electrons
Geometry
Graph theory
Mathematical minima
Metastability
Probability distribution
Random variables
sharp threshold
Stein–Chen method
Studies
Vertices
Zero
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let r ϵ ℕ. 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(logn/loglogn), 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.
ISSN:0091-1798
2168-894X
2168-894X
DOI:10.1214/12-AOP818