Linear algebra and bootstrap percolation

Journal article

In $\HH$-bootstrap percolation, a set $A \subset V(\HH)$ of initially 'infected' vertices spreads by infecting vertices which are the only uninfected vertex in an edge of the hypergraph $\HH$. A particular case of this is the $H$-bootstrap process, in which $\HH$ 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 $\HH$ 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.

Authors: Balogh, J; Bollobás, B; Morris, R; Riordan, O

• Publication status: Published
• Journal: JOURNAL OF COMBINATORIAL THEORY SERIES A
• Volume: 119
• Issue: 6
• Pages: 1328-1335
• Publication date: 2011-07-07
• DOI: 10.1016/j.jcta.2012.03.005
• EISSN: 1096-0899
• ISSN: 0097-3165
• Language: English
• Keywords: math.CO