Contagious Sets in Random Graphs

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 \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}}$. Assuming $r>1$ to be a constant that does not depend on $n$, we prove that $$m(G,r)=\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 }=\Theta \left(\frac{1}{(n{\log }^{r-1}n{)}^{1/r}}\right)$.