TY - JOUR
T1 - Linear algebra and bootstrap percolation
AU - Balogh, József
AU - Bollobás, Béla
AU - Morris, Robert
AU - Riordan, Oliver
N1 - Funding Information:
✩ Research supported in part by: (J.B.) NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grants 09072 and 11067, OTKA Grant K76099, and the TAMOP-4.2.1/B-09/1/KONV-2010-0005 project; (B.B.) NSF grants DMS-0906634, CNS-0721983 and CCF-0728928, ARO grant W911NF-06-1-0076, and TAMOP-4.2.2/08/1/2008-0008 program of the Hungarian Development Agency; (R.M.) CNPq bolsa de Produtividade em Pesquisa. E-mail addresses: [email protected] (J. Balogh), [email protected] (B. Bollobás), [email protected] (R. Morris), [email protected] (O. Riordan).
PY - 2012/8
Y1 - 2012/8
N2 - 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.
AB - 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.
KW - Bootstrap percolation
KW - Linear algebra
KW - Weak saturation
UR - http://www.scopus.com/inward/record.url?scp=84858975450&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84858975450&partnerID=8YFLogxK
U2 - 10.1016/j.jcta.2012.03.005
DO - 10.1016/j.jcta.2012.03.005
M3 - Article
AN - SCOPUS:84858975450
SN - 0097-3165
VL - 119
SP - 1328
EP - 1335
JO - Journal of Combinatorial Theory. Series A
JF - Journal of Combinatorial Theory. Series A
IS - 6
ER -