Contagious Sets in Random Graphs

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 \emph{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 $p: = \frac{d}{n}$and$1 \ll d \ll \left(\frac{n \log \log n}{\log^2 n}\right)^{\frac{r-1}{r}}$\mathrm{.}Assuming$r > 1$ to be a constant that does not depend on $n$, we prove that $$m(G,r)=\mathrm{\Theta }\left(\frac{n}{d^{\frac{r}{r-1}}\log d}\right),$$ with high probability. We also show that the threshold probability for $m(G,r)=r$ to hold is $p^{\ast }=\mathrm{\Theta }\left(\frac{1}{(n{\log }^{r-1}n{)}^{1\mathrm{/}r}}\right)$.