Lower bounds for bootstrap percolation on Galton-Watson trees

Karen Gunderson (Heilbronn Institute, University of Bristol)
Michal Przykucki (University of Cambridge and London Institute for Mathematical Sciences)

Abstract


Bootstrap percolation is a cellular automaton modelling the spread of an `infection' on a graph. In this note, we prove a family 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ás, 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 Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-7

Publication Date: July 12, 2014

DOI: 10.1214/ECP.v19-3315

References

  • J. Chalupa, P.L. Leath, and G.R. Reich, phBootstrap percolation on a Bethe latice, J. Phys. C, 12 (1979), L31--L35.
  • Balogh, József; Peres, Yuval; Pete, Gábor. Bootstrap percolation on infinite trees and non-amenable groups. Combin. Probab. Comput. 15 (2006), no. 5, 715--730. MR2248323
  • Bollobás, Béla; Gunderson, Karen; Holmgren, Cecilia; Janson, Svante; Przykucki, Michał. Bootstrap percolation on Galton-Watson trees. Electron. J. Probab. 19 (2014), no. 13, 27 pp. MR3164766
  • Gautschi, Walter. Some elementary inequalities relating to the gamma and incomplete gamma function. J. Math. and Phys. 38 1959/60 77--81. MR0103289
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.