An Improved Upper Bound for Bootstrap Percolation in All Dimensions
Andrew J. Uzzell · Combinatorics Probability Computing · 2019
Abstract In r -neighbour 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 neighbours. 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 ⩾ r ⩾ 2. We show that for all d ⩾ r ⩾ 2 there exists a constant c d , r > 0 such that if n is sufficiently large, then $$p_c (\left[ n \right]^d ,{\rm{ }}r){\rm{\le }}\left( {\frac{{\lambda (d,r)}}{{\log _{(r - 1)} (n)}} - \frac{{c_{d,r} }}{{(\log _{(r - 1)} (n))^{3/2} }}} \right)^{d - r + 1} ,$$ where λ ( d, r ) is an exact constant and log (k) ( n ) denotes the k -times iterated natural logarithm of n .