Change search
ReferencesLink to record
Permanent link

Direct link
Bootstrap percolation on Galton-Watson trees
Stockholm University, Faculty of Science, Department of Mathematics.
Show others and affiliations
2014 (English)In: Electronic Journal of Probability, ISSN 1083-6489, Vol. 19, 1-27 p.Article in journal (Refereed) Published
Abstract [en]

Bootstrap percolation is a type of cellular automaton which has been used to model various physical phenomena, such as ferromagnetism. For each natural number r, the r-neighbour bootstrap process is an update rule for vertices of a graph in one of two states: 'infected' or 'healthy'. In consecutive rounds, each healthy vertex with at least r infected neighbours becomes itself infected. Percolation is said to occur if every vertex is eventually infected. Usually, the starting set of infected vertices is chosen at random, with all vertices initially infected independently with probability p. In that case, given a graph G and infection threshold r, a quantity of interest is the critical probability, p(c)(G, r), at which percolation becomes likely to occur. In this paper, we look at infinite trees and, answering a problem posed by Balogh, Peres and Pete, we show that for any b >= r and for any epsilon > 0 there exists a tree T with branching number br(T) = b and critical probability p(c)(T, r) < epsilon. However, this is false if we limit ourselves to the well-studied family of Galton-Watson trees. We show that for every r >= 2 there exists a constant c(r) > 0 such that if T is a Galton-Watson tree with branching number br(T) - b >= r then pc (T, r) > c(r)/b e(-b/r-1). We also show that this bound is sharp up to a factor of O (b) by giving an explicit family of Galton-Watson trees with critical probability bounded from above by C(r)e(-b/r-1) for some constant C-r > 0.

Place, publisher, year, edition, pages
Univ. of Washington, Washington, USA , 2014. Vol. 19, 1-27 p.
Keyword [en]
bootstrap percolation, branching number, infinite trees, Galton-Watson trees
National Category
Probability Theory and Statistics
URN: urn:nbn:se:su:diva-101749DOI: 10.1214/EJP.v19-2758ISI: 000331471000001OAI: diva2:705854
Swedish Research CouncilKnut and Alice Wallenberg Foundation


Other Funders:

NSF DMS 1301614;  MULTIPLEX 317532 

Available from: 2014-03-18 Created: 2014-03-14 Last updated: 2014-03-18Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Holmgren, Cecilia
By organisation
Department of Mathematics
In the same journal
Electronic Journal of Probability
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 29 hits
ReferencesLink to record
Permanent link

Direct link