## Abstract

In r-neighbour bootstrap percolation on a graph G, a set of initially infected vertices A ⊂ V(G) is chosen independently at random, with density p, and new vertices are subsequently infected if they have at least r infected neighbours. The set A is said to percolate if eventually all vertices are infected. Our aim is to understand this process on the grid, [n]^{d}, for arbitrary functions n = n(t), d = d(t) and r = r(t), as t → ∞. The main question is to determine the critical probability pc([n]^{d}, r) at which percolation becomes likely, and to give bounds on the size of the critical window. In this paper we study this problem when r = 2, for all functions n and d satisfying d ≫ log n. The bootstrap process has been extensively studied on [n]^{d} when d is a fixed constant and 2 ≤ r ≤ d, and in these cases pc([n]^{d}, r) has recently been determined up to a factor of 1 + o(1) as n → ∞. At the other end of the scale, Balogh and Bollobás determined pc([2]^{d}, 2) up to a constant factor, and Balogh, Bollobás and Morris determined pc([n]^{d}, d) asymptotically if d ≥ (log log n)^{2+ε}, and gave much sharper bounds for the hypercube. Here we prove the following result. Let λ be the smallest positive root of the equation Σ^{∞} _{k=0}(-1)^{k}λ^{k}/2k^{2}-kK! = 0, so λ ≈ 1.166. Then 16λ/d^{2}(1 + logd/√d)2 ^{-2√d} ≤ pc([2]^{d}, 2) ≤ 16λ/d^{2} (1 + 5(log d)^{2}/√d) 2^{-2√d} if d is sufficiently large, and moreover equation presented as d → ∞, for every function n = n(d) with d ≫ log n.

Original language | English (US) |
---|---|

Pages (from-to) | 643-692 |

Number of pages | 50 |

Journal | Combinatorics Probability and Computing |

Volume | 19 |

Issue number | 5-6 |

DOIs | |

State | Published - Sep 2010 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics