Contagious sets in random graphs

Citation
Feige,uriel et al., Contagious sets in random graphs, Annals of applied probability , 27(5), 2017, pp. 2675-2697
ISSN journal
10505164
Volume
27
Issue
5
Year of publication
2017
Pages
2675 - 2697
Database
ACNP
SICI code
Abstract
We consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least r active neighbors. A contagious set is a set whose activation results with the entire graph being active. Given a graph G, let m(G, r) be the minimal size of a contagious set. We study this process on the binomial random graph G := G(n, p) with $\mathrm{p}:=\frac{\mathrm{d}}{\mathrm{n}}$ and $1\ll \mathrm{d}\ll (\frac{\mathrm{n} \ \mathrm{log} \ \mathrm{log} \ \mathrm{n}}{{\mathrm{log}}^{\mathrm{n}}\mathrm{n}}{)}^{\frac{\mathrm{r}-1}{\mathrm{r}}}$. Assuming r > 1 to be a constant that does not depend on n, we prove that $\mathrm{m}(\mathrm{G},\mathrm{r})=\mathrm{\Theta }\left(\frac{\mathrm{n}}{{\mathrm{d}}^{\frac{\mathrm{r}}{\mathrm{r}-1}}\mathrm{log}\mathrm{d}}\right)$, with high probability. We also show that the threshold probability for m(G, r) = r to hold is ${\mathrm{p}}^{*}=\mathrm{\Theta }\left(\frac{1}{(\mathrm{n} \ {\mathrm{log}}^{\mathrm{r}-1} \mathrm{n}{)}^{1/\mathrm{r}}}\right)$.