Bootstrap percolation on the random graph Gn,p
(2012) In Annals of Applied Probability 22(5). p.1989-2047- Abstract
- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/3244520
- author
- Janson, Svante ; Luczak, Tomasz ; Turova, Tatyana LU and Vallier, Thomas
- organization
- publishing date
- 2012
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Bootstrap percolation, random graph, sharp threshold
- in
- Annals of Applied Probability
- volume
- 22
- issue
- 5
- pages
- 1989 - 2047
- publisher
- Institute of Mathematical Statistics
- external identifiers
-
- wos:000310931400008
- scopus:84871621991
- ISSN
- 1050-5164
- DOI
- 10.1214/11-AAP822
- language
- English
- LU publication?
- yes
- id
- 32ee2f70-e3a1-4c1b-9259-0e45af315727 (old id 3244520)
- date added to LUP
- 2016-04-01 13:08:03
- date last changed
- 2022-03-29 05:45:19
@article{32ee2f70-e3a1-4c1b-9259-0e45af315727,
abstract = {{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.}},
author = {{Janson, Svante and Luczak, Tomasz and Turova, Tatyana and Vallier, Thomas}},
issn = {{1050-5164}},
keywords = {{Bootstrap percolation; random graph; sharp threshold}},
language = {{eng}},
number = {{5}},
pages = {{1989--2047}},
publisher = {{Institute of Mathematical Statistics}},
series = {{Annals of Applied Probability}},
title = {{Bootstrap percolation on the random graph Gn,p}},
url = {{http://dx.doi.org/10.1214/11-AAP822}},
doi = {{10.1214/11-AAP822}},
volume = {{22}},
year = {{2012}},
}