Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Bootstrap percolation on Galton-Watson trees
Stockholms universitet, Naturvetenskapliga fakulteten, Matematiska institutionen.
Vise andre og tillknytning
2014 (engelsk)Inngår i: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 19, s. 1-27Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Univ. of Washington, Washington, USA , 2014. Vol. 19, s. 1-27
Emneord [en]
bootstrap percolation, branching number, infinite trees, Galton-Watson trees
HSV kategori
Identifikatorer
URN: urn:nbn:se:su:diva-101749DOI: 10.1214/EJP.v19-2758ISI: 000331471000001OAI: oai:DiVA.org:su-101749DiVA, id: diva2:705854
Forskningsfinansiär
Swedish Research CouncilKnut and Alice Wallenberg Foundation
Merknad

AuthorCount:5;

Other Funders:

NSF DMS 1301614;  MULTIPLEX 317532 

Tilgjengelig fra: 2014-03-18 Laget: 2014-03-14 Sist oppdatert: 2017-12-05bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Søk i DiVA

Av forfatter/redaktør
Holmgren, Cecilia
Av organisasjonen
I samme tidsskrift
Electronic Journal of Probability

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 67 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf