Contagious sets in random graphs (Q1688015)

The authors consider the classical bootstrap percolation process on a binomial random graph \(G(n,p)\). A set of vertices is called contagious, if the bootstrap process percolates when this set is the set of initially active vertices. The authors of this paper consider the typical size of a smallest percolating set in a \(G(n,p)\) random graph. Expressing \(p=d/n\), they give the typical order of magnitude of a smallest contagious set in \(G(n,d/n)\), for \(d\gg 1\) but \(d\) growing at most like a polynomial of order \(n^{(r-1)/r}\) (together with some logarithmic factors), where \(r\) is the activation parameter of the bootstrap process. They also consider the question about when this minimum size of a contagious set could be equal to \(r\), that is, there exists a set of only \(r\) vertices such that if only these are active in the beginning of the process, then it percolates. They give the critical function \(p^\ast=p^\ast(n)\) (up to multiplicative constants) such that when \(p \gg p^\ast\), then such a set of size \(r\) exists, but when \(p\ll p^\ast\), it does not.