Lower bounds for bootstrap percolation on Galton-Watson trees

DOI10.1214/ECP.V19-3315zbMATH Open1298.05064arXiv1402.4462OpenAlexW1972590410MaRDI QIDQ457796FDOQ457796

Authors: Karen Gunderson, Michał Przykucki 

Publication date: 29 September 2014

Published in: Electronic Communications in Probability (Search for Journal in Brave)

Abstract: Bootstrap percolation is a cellular automaton modelling the spread of an `infection' on a graph. In this note, we prove a family of lower bounds on the critical probability for $r$-neighbour bootstrap percolation on Galton--Watson trees in terms of moments of the offspring distributions. With this result we confirm a conjecture of Bollob'as, Gunderson, Holmgren, Janson and Przykucki. We also show that these bounds are best possible up to positive constants not depending on the offspring distribution.

Full work available at URL: https://arxiv.org/abs/1402.4462

Recommendations

• Bootstrap percolation on Galton-Watson trees
• An improved upper bound for bootstrap percolation in all dimensions
• Bootstrap Percolation on Periodic Trees
• Bootstrap percolation on G(n,p) revisited
• Metastable behavior of bootstrap percolation on Galton-Watson trees

zbMATH Keywords

bootstrap percolationGalton-Watson trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Cellular automata (computational aspects) (68Q80)

Cited In (5)

• Metastable behavior of bootstrap percolation on Galton-Watson trees
• Bootstrap percolation on homogeneous trees has 2 phase transitions
• Bootstrap percolation on Galton-Watson trees
• The cone percolation model on Galton-Watson and on spherically symmetric trees
• Deterministic bootstrap percolation on trees

This page was built for publication: Lower bounds for bootstrap percolation on Galton-Watson trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q457796)