2011/07/07 by József Balogh, Balogh, József, Béla Bollobás +5 · 2 citations
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #math.CO
paper · pdf · doi:10.48550/arxiv.1107.1410
10 pages
openalex publication_date 2011/07/07 · arxiv created 2012/02/25 · arxiv updated 2012/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In \HH-bootstrap percolation, a set A ⊂ 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.