Name
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 \[\sum_{k=0}^\infty \frac{(-1)^k \lambda^k}{2^{k^2-k} k!} = 0,\] so λ ≈ 1.166. Then \[ \frac{16\lambda}{d^2} \biggl(1 + \frac{\log d}{\sqrt{d}} \biggr)\: 2^{-2\sqrt{d}} \leq p_c([2]^d,2) \leq \frac{16\lambda}{d^2} \biggl(1 + \frac{5(\log d)^2}{\sqrt{d}} \biggr) \: 2^{-2\sqrt{d}}\] if d is sufficiently large, and moreover \[p_c\bigl([n]^d,2 \bigr) = \bigl(4\lambda + o(1) \bigr) \biggl(\frac{n}{n-1} \biggr)^2 \, \frac{1}{d^2} \, 2^{-2\sqrt{d \log_2 n}}\] as d → ∞, for every function n = n(d) with d ≫ log n. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1017/S0963548310000271 | Combinatorics, Probability & Computing |
Keywords | DocType | Volume |
log log n,function n,functions n,infected vertex,critical probability pc,r infected neighbour,arbitrary functions n,log_2 n,high dimension,bootstrap percolation,log n,cases pc,satisfiability | Journal | 19 |
Issue | ISSN | Citations |
5-6 | 0963-5483 | 9 |
PageRank | References | Authors |
0.97 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Béla Bollobás | 2 | 2696 | 474.16 |
| Robert Morris | 3 | 101 | 13.12 |