Mathematics – Combinatorics
Scientific paper
2008-06-27
Annals of Probability 2009, Vol. 37, No. 4, 1329-1380
Mathematics
Combinatorics
Published in at http://dx.doi.org/10.1214/08-AOP433 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of
Scientific paper
10.1214/08-AOP433
By bootstrap percolation we mean the following deterministic process on a graph $G$. Given a set $A$ of vertices "infected" at time 0, new vertices are subsequently infected, at each time step, if they have at least $r\in\mathbb{N}$ previously infected neighbors. When the set $A$ is chosen at random, the main aim is to determine the critical probability $p_c(G,r)$ at which percolation (infection of the entire graph) becomes likely to occur. This bootstrap process has been extensively studied on the $d$-dimensional grid $[n]^d$: with $2\leq r\leq d$ fixed, it was proved by Cerf and Cirillo (for $d=r=3$), and by Cerf and Manzo (in general), that \[p_c([n]^d,r)=\Theta\biggl(\frac{1}{\log_{(r-1)}n}\biggr)^{d-r+1},\] where $\log_{(r)}$ is an $r$-times iterated logarithm. However, the exact threshold function is only known in the case $d=r=2$, where it was shown by Holroyd to be $(1+o(1))\frac{\pi^2}{18\log n}$. In this paper we shall determine the exact threshold in the crucial case $d=r=3$, and lay the groundwork for solving the problem for all fixed $d$ and $r$.
Balogh József
Bollobas Bela
Morris Robert
No associations
LandOfFree
Bootstrap percolation in three dimensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bootstrap percolation in three dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bootstrap percolation in three dimensions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-692735