Contagious sets in a degree-proportional bootstrap percolation process

Abstract

We study the following bootstrap percolation process: given a connected graph $G$, a constant $\rho \in [0,1]$ and an initial set $A\subseteq V(G)$ of \emph{infected} vertices, at each step a vertex~$v$ becomes infected if at least a $\rho$-proportion of its neighbours are already infected (once infected, a vertex remains infected forever). Our focus is on the size $h_{\rho }(G)$ of a smallest initial set which is \emph{contagious}, meaning that this process results in the infection of every vertex of $G$. Our main result states that every connected graph $G$ on $n$ vertices has $h_{\rho }(G)<2\rho n$ or $h_{\rho }(G)=1$ (note that allowing the latter possibility is necessary because of the case $\rho \le \frac{1}{2n}$, as every contagious set has size at least one). This is the best-possible bound of this form, and improves on previous results of Chang and Lyuu and of Gentner and Rautenbach. We also provide a stronger bound for graphs of girth at least five and sufficiently small $\rho$, which is asymptotically best-possible.

14 pages, 1 figure