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. This process (commonly referred to as bootstrap percolation) has been studied in several fields including statistical physics, computer science, and combinatorics.
We study this process in the binomial random graph G:=G(n,p). Assuming r>1 to be a fixed constant, we determine the asymptotic value of m(G,r) (holding with high probability). Our proof is constructive in the sense that it entails a polynomial algorithm for finding nearly optimal contagious sets.
We also determine the asymptotic threshold probability for G(n,p) to satisfy m(G,r)=r.
Based on joint work with Uriel Feige (Weizmann) and Michael Krivelevich (Tel Aviv).