Bootstrap percolation in three dimensions

By Jozsef Balogh, Béla Bollobás, Robert Morris. 2008

114 citations recorded by the source corpus.

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 ∈ 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 ≤ r ≤ 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)=Θ(1/log (r-1) n) 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)) π 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.

Subfields: Condensed Matter Physics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/d1d89b9790ae12459dfbe18ba4f9099a04c57d0c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Majority bootstrap percolation on the random graph G(n,p) (2010, result): “(These references also treat higherdimensional grids [n]d.) Another extremal problem is studied by Morris [39].”
The sharp threshold for bootstrap percolation in all dimensions (2010, methodology): “In this section we recall various tools and deﬁnitions from [6] where [ a, b ] = { a, a +1 , . . . , b } and [ b ] = [1 , b ].”