Advanced

Bootstrap percolation on the random graph Gn,p

Janson, Svante; Luczak, Tomasz; Turova, Tatyana LU and Vallier, Thomas (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:
author
organization
publishing date
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
2012-12-27 11:55:58
date last changed
2017-11-12 03:35:18
@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},
  keyword      = {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},
  volume       = {22},
  year         = {2012},
}