An Improved Upper Bound for Bootstrap Percolation in All Dimensions

Abstract

In $r$-neighbor bootstrap percolation on the vertex set of a graph $G$, a set $A$ of initially infected vertices spreads by infecting, at each time step, all uninfected vertices with at least $r$ previously infected neighbors. When the elements of $A$ are chosen independently with some probability $p$, it is natural to study the critical probability $p_c(G,r)$ at which it becomes likely that all of $V(G)$ will eventually become infected. Improving a result of Balogh, Bollobás, and Morris, we give a bound on the second term in the expansion of the critical probability when $G=[n{]}^d$ and $d\ge r\ge 2$. We show that for all $d\ge r\ge 2$ there exists a constant $c_{d,r}>0$ such that if $n$ is sufficiently large, then \[ p_c([n]^d, r) \leq \Biggl(\dfrac{λ(d,r)}{\log_{(r-1)}(n)} - \dfrac{c_{d,r}}{\bigl(\log_{(r-1)}(n)\bigr)^{3/2}}\Biggr)^{d-r+1}, \] where $\lambda (d,r)$ is an exact constant and ${\log }_{(k)}(n)$ denotes the $k$-times iterated natural logarithm of $n$.

30 pages, 3 figures. Substantially revised

References in corpus (6)

• Bootstrap percolation on the random graph $G_{n,p}$
• Bootstrap percolation in three dimensions
• Monotone cellular automata in a random environment
• Sharp metastability threshold for an anisotropic bootstrap percolation model
• The second term for two-neighbour bootstrap percolation in two dimensions
• Metastability threshold for anisotropic bootstrap percolation in three dimensions

Cited by in corpus (4)

• The second term for two-neighbour bootstrap percolation in two dimensions
• Sharp threshold for the FA-2f kinetically constrained model
• Bootstrap percolation on a graph with random and local connections
• Irreversible 2-conversion set in graphs of bounded degree