Last updated
2025-04-11T14:35:29.83+01:00
Abstract
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.
'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.
Symplectic ID
164004
Download URL
http://arxiv.org/abs/1107.1410v2
Submitted to ORA
Off
Favourite
Off
Publication type
Journal Article
Publication date
07 Jul 2011