Bootstrap percolation on the random graph Gn,p
(2012) In Annals of Applied Probability 22(5). p.19892047 Abstract
 Bootstrap percolation on the random graph Cn,Cp 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 Cn,Cp 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:
http://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
 10505164
 DOI
 10.1214/11AAP822
 language
 English
 LU publication?
 yes
 id
 32ee2f70e3a14c1b92590e45af315727 (old id 3244520)
 date added to LUP
 20121227 11:55:58
 date last changed
 20171112 03:35:18
@article{32ee2f70e3a14c1b92590e45af315727, abstract = {Bootstrap percolation on the random graph Cn,Cp 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 = {10505164}, keyword = {Bootstrap percolation,random graph,sharp threshold}, language = {eng}, number = {5}, pages = {19892047}, 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/11AAP822}, volume = {22}, year = {2012}, }