Graph bootstrap percolation

József Balogh, Béla Bollobás, Robert Morris

Research output: Contribution to journalArticlepeer-review

Abstract

Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollobás in 1968, and is defined as follows. Given a graph H, and a set G ⊂ E(K n) of initially 'infected' edges, we infect, at each time step, a new edge e if there is a copy of H in K n such that e is the only not-yet infected edge of H. We say that G percolates in the H-bootstrap process if eventually every edge of K n is infected. The extremal questions for this model, when H is the complete graph K r, were solved (independently) by Alon, Kalai and Frankl almost thirty years ago. In this paper we study the random questions, and determine the critical probability p c(n,K r) for the K r-process up to a poly-logarithmic factor. In the case r = 4 we prove a stronger result, and determine the threshold for p c(n,K 4).

Original languageEnglish (US)
Pages (from-to)413-440
Number of pages28
JournalRandom Structures and Algorithms
Volume41
Issue number4
DOIs
StatePublished - Dec 2012

Keywords

  • Bootstrap percolation
  • Graph theory
  • Weak saturation

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Graph bootstrap percolation'. Together they form a unique fingerprint.

Cite this