Bootstrap percolation on the random regular graph

• Published in: Random structures & algorithms 2007-01, Vol.30 (1-2), p.257-286
• Main Authors: Balogh, József, Pittel, Boris G.
• Format: Article
• Language: English
• Subjects: cellular automata; percolation; random regular graph
• ISSN: 1042-9832; 1098-2418
• DOI: 10.1002/rsa.20158

The k‐parameter bootstrap percolation on a graph is a model of an interacting particle system, which can also be viewed as a variant of a cellular automaton growth process with threshold k ≥ 2. At the start, each of the graph vertices is active with probability p and inactive with probability 1 − p, independently of other vertices. Presence of active vertices triggers a bootstrap percolation process controlled by a recursive rule: an active vertex remains active forever, and a currently inactive vertex becomes active when at least k of its neighbors are active. The basic problem is to identify, for a given graph, p− and p+ such that for p < p− (p > p+ resp.) the probability that all vertices are eventually active is very close to 0 (1 resp.). The bootstrap percolation process is a deterministic process on the space of subsets of the vertex set, which is easy to describe but hard to analyze rigorously in general. We study the percolation on the random d‐regular graph, d ≥ 3, via analysis of the process on the multigraph counterpart of the graph. Here, thanks to a “principle of deferred decisions,” the percolation dynamics is described by a surprisingly simple Markov chain. Its generic state is formed by the counts of currently active and nonactive vertices having various degrees of activation capabilities. We replace the chain by a deterministic dynamical system, and use its integrals to show—via exponential supermartingales—that the percolation process undergoes relatively small fluctuations around the deterministic trajectory. This allows us to show existence of the phase transition within an interval [p−(n),p+(n)], such that (1) p±(n) → p* = 1 − miny∈(0,1)y/ℙ(Bin(d − 1,1 − y) < k); (2) p+(n) − p−(n) is of order n−1/2 for k < d − 1, and n −ε n, (εn ↓ 0,εn log n →∞), for k = d − 1. Note that p* is the same as the critical probability of the process on the corresponding infinite regular tree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 30, 257–286, 2007