Linear algebra and bootstrap percolation

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

Research output: Contribution to journalArticlepeer-review


In H-bootstrap percolation, a set A⊂V(H) of initially 'infected' vertices spreads by infecting vertices which are the only uninfected vertex in an edge of the hypergraph H. A particular case of this is the H-bootstrap process, in which H encodes copies of H in a graph G. We find the minimum size of a set A that leads to complete infection when G and H are powers of complete graphs and H encodes induced copies of H in G. The proof uses linear algebra, a technique that is new in bootstrap percolation, although standard in the study of weakly saturated graphs, which are equivalent to (edge) H-bootstrap percolation on a complete graph.

Original languageEnglish (US)
Pages (from-to)1328-1335
Number of pages8
JournalJournal of Combinatorial Theory. Series A
Issue number6
StatePublished - Aug 2012


  • Bootstrap percolation
  • Linear algebra
  • Weak saturation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


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

Cite this