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 the random graph Gn,p
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
2012 (English)In: The Annals of Applied Probability, ISSN 1050-5164, E-ISSN 2168-8737, Vol. 22, no 5, 1989-2047 p.Article in journal (Refereed) Published
Abstract [en]

Bootstrap percolation on the random graph C-n,C-p is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least r >= 2 active neighbors become active as well. We study the size A* of the final active set. The parameters of the model are, besides r (fixed) and n (tending to infinity), the size a = a(n) of the initially active set and the probability p = p(n) of the edges in the graph. We show that the model exhibits a sharp phase transition: depending on the parameters of the model, the final size of activation with a high probability is either n - o(n) or it is o(n). We provide a complete description of the phase diagram on the space of the parameters of the model. In particular, we find the phase transition and compute the asymptotics (in probability) for A*; we also prove a central limit theorem for A* in some ranges. Furthermore, we provide the asymptotics for the number of steps until the process stops.

Place, publisher, year, edition, pages
2012. Vol. 22, no 5, 1989-2047 p.
Keyword [en]
Bootstrap percolation, random graph, sharp threshold
National Category
Natural Sciences
Identifiers
URN: urn:nbn:se:uu:diva-188560DOI: 10.1214/11-AAP822ISI: 000310931400008OAI: oai:DiVA.org:uu-188560DiVA: diva2:578547
Available from: 2012-12-18 Created: 2012-12-17 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Janson, Svante

Search in DiVA

By author/editor
Janson, Svante
By organisation
Analysis and Applied Mathematics
In the same journal
The Annals of Applied Probability
Natural Sciences

Search outside of DiVA

GoogleGoogle Scholar

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