Linear algebra and bootstrap percolation

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:119

Article

Balogh, Jozsef^1,2  Bollobas, Bela^3,4  Morris, Robert⁵  Riordan, Oliver⁶ 

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[2] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA

[3] Univ Cambridge Trinity Coll, Cambridge CB2 1TQ, England

[4] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA

[5] IMPA, Rio De Janeiro, RJ, Brazil

[6] Univ Oxford, Math Inst, Oxford OX1 3LB, England

关键词: Bootstrap percolation;    Linear algebra;    Weak saturation;   

DOI  :  10.1016/j.jcta.2012.03.005

来源: Elsevier

【 摘 要 】

In H-bootstrap percolation, a set A subset of 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. (C) 2012 Elsevier Inc. All rights reserved.

【 授权许可】

Free