Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 1328-1335 |
| Number of pages | 8 |
| Journal | Journal of Combinatorial Theory. Series A |
| Volume | 119 |
| Issue number | 6 |
| DOIs | |
| State | Published - Aug 2012 |
Keywords
- Bootstrap percolation
- Linear algebra
- Weak saturation
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Fingerprint
Dive into the research topics of 'Linear algebra and bootstrap percolation'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS