uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, E-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
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-220817DOI: 10.1214/EJP.v19-2758ISI: 000331471000001OAI: oai:DiVA.org:uu-220817DiVA: diva2:706624
Available from: 2014-03-21 Created: 2014-03-20 Last updated: 2017-12-05Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full text

Authority records BETA

Holmgren, CeciliaJanson, Svante

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 45 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 404 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf