Bootstrap percolation on the random regular graph

Jozsef Balog, Boris G. Pittel

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)257-286
Number of pages30
JournalRandom Structures and Algorithms
Volume30
Issue number1-2
DOIs
StatePublished - Jan 1 2007

Keywords

  • Cellular automata
  • Percolation
  • Random regular graph

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Bootstrap percolation on the random regular graph'. Together they form a unique fingerprint.

Cite this