Bootstrap Percolation in d Dimensions

  • Date: 04/19/2006

Alexander Holroyd (University of British Columbia)


University of British Columbia


Modified bootstrap percolation is a very simple cellular automaton
model for nucleation and growth. Sites in the cube {1,...,L}^d are
initially occupied independently with probability p. At subsequent
steps, an unoccupied site becomes occupied if it has at one occupied
neighbour in each of the d dimensions. It turns out that for any
p>0, the entire cube becomes occupied (with high probability) if L
is large enough. One can ask how large L needs to be for this to
happen. For d>=2, the answer is (approximately) exp exp ... exp
(lambda/p), where the exponential is iterated d-1 times, and the
constant lambda equals pi^2/6. This is proved by a surprising induction
on the dimension.

The modified model above is a seemingly innocuous variation on the
'standard' bootstrap percolation model, in which a site becomes
occupied if it has at least d occupied neighbours. However, the
existence of a sharp threshold lambda as above is unproved for the
standard model, except in the case d=2, where the threshold occurs at
exp(lambda'/p), with lambda'= pi^2/18.

See for a picture of the standard model in d=2.

Other Information: 

Probability Seminar 2006