Bootstrap percolation on the random graph G_n,p

DOI10.1214/11-AAP822MaRDI QIDQ691111zbMATH OpenFDO

Authors Svante Janson, Tomasz Łuczak, Thomas Vallier, Tatyana S. Turova

Publication date 29 November 2012

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.3535, https://projecteuclid.org/euclid.aoap/1350067992

bootstrap percolation random graph sharp threshold

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: Bootstrap percolation on the random graph

G_{n, 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 g e q 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

i n f t y

), 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.

Recommendations

Cites work

Cited in

(86)

This page was built for publication: Bootstrap percolation on the random graph \(G_{n,p}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q691111)