Lower bounds for bootstrap percolation on Galton-Watson trees

DOI10.1214/ECP.V19-3315MaRDI QIDQ457796zbMATH OpenOpenAlexFDO

Authors Karen Gunderson, Michał Przykucki

Publication date 29 September 2014

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

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

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)

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.

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

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)