Combinatorics, Probability and Computing


Bootstrap Percolation on Infinite Trees and Non-Amenable Groups

a1 Department of Mathematics, The Ohio State University, 231 W 18th Ave, Columbus, OH 43235, USA (e-mail:
a2 Departments of Statistics and Mathematics, 367 Evans Hall, University of California, Berkeley, CA 94720, USA (e-mail:
a3 Department of Statistics, 367 Evans Hall, University of California, Berkeley, CA 94720, USA (e-mail:

Article author query
balogh j   [Google Scholar] 
peres y   [Google Scholar] 
pete g   [Google Scholar] 


Bootstrap percolation on an arbitrary graph has a random initial configuration, where each vertex is occupied with probability $p$, independently of each other, and a deterministic spreading rule with a fixed parameter $k$: if a vacant site has at least $k$ occupied neighbours at a certain time step, then it becomes occupied in the next step. This process is well studied on ${\mathbb Z}^d$; here we investigate it on regular and general infinite trees and on non-amenable Cayley graphs. The critical probability is the infimum of those values of $p$ for which the process achieves complete occupation with positive probability. On trees we find the following discontinuity: if the branching number of a tree is strictly smaller than $k$, then the critical probability is 1, while it is $1-1/k$ on the $k$-ary tree. A related result is that in any rooted tree $T$ there is a way of erasing $k$ children of the root, together with all their descendants, and repeating this for all remaining children, and so on, such that the remaining tree $T'$ has branching number $\mbox{\rm br}(T')\leq \max\{\mbox{\rm br}(T)-k,\,0\}$. We also prove that on any $2k$-regular non-amenable graph, the critical probability for the $k$-rule is strictly positive.

(Published Online July 31 2006)
(Received January 27 2004)
(Revised September 25 2004)


1 Partially supported by NSF grant DMS-0302804 and OTKA (Hungarian National Foundation for Scientific Research) grant T34475.

2 Partially supported by NSF grants DMS-0104073 and DMS-0244479.

3 Partially supported by NSF grants DMS-0104073 and DMS-0244479