Change search
ReferencesLink to record
Permanent link

Direct link
Bootstrap percolation on Galton-Watson trees
Stockholms universitet.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer 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
2014. Vol. 19, 1-27 p.
Keyword [en]
bootstrap percolation, branching number, infinite trees, Galton-Watson trees
National Category
URN: urn:nbn:se:uu:diva-220817DOI: 10.1214/EJP.v19-2758ISI: 000331471000001OAI: diva2:706624
Available from: 2014-03-21 Created: 2014-03-20 Last updated: 2015-08-19Bibliographically approved

Open Access in DiVA

fulltext(446 kB)30 downloads
File information
File name FULLTEXT01.pdfFile size 446 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Holmgren, CeciliaJanson, Svante
By organisation
Department of Mathematics
In the same journal
Electronic Journal of Probability

Search outside of DiVA

GoogleGoogle Scholar
Total: 30 downloads
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: 202 hits
ReferencesLink to record
Permanent link

Direct link