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

Direct link
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, 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
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: 2012-12-18Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

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
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: 187 hits
ReferencesLink to record
Permanent link

Direct link