Bootstrap percolation on Galton-Watson trees (Q2637757)

This paper is a study of the critical initial infection probability for a bootstrap percolation process. A bootstrap percolation process on a graph \(G\) is an infection process where at any round, if an uninfected vertex has at least \(r\geq 2\) infected neighbors, then it becomes infected and remains so. The parameter \(r\) is common to every vertex. It is a common assumption that the initial infected set is chosen randomly, where each vertex is infected with probability \(p\) independently of any other vertex. The critical probability is the smallest \(p\) for which the process infects every vertex of \(G\) with probability at least 1/2. This parameter is considered when \(G\) is a tree. The first theorem regards the class of regular trees with bounded degree and branching number at most \(b\). It is shown that if \(b \geq r\), then the minimum critical probability over all such trees is 0. More precisely, such trees with arbitrarily small critical probability are constructed. This completes a result of \textit{J. Balogh} et al. [Comb. Probab. Comput. 15, No. 5, 715--730 (2006; Zbl 1102.60086)]. Further, the sub-class of trees that are the outcome of a Galton-Watson process are considered. Assume now that \(b\) denotes the expected number of offsprings. Assume also that the offspring distribution produces no offspring with probability 0. If \(r> b \geq 1\), then this critical probability is 1 for all choices of the offspring distribution that satisfies the above premises. For \(b \geq r\), the smallest critical probability is estimated as a function of \(r\) and \(b\). Furthermore, for a given offspring distribution the critical probability is estimated as a function of certain moments of this distribution. It becomes more specific for the case \(r=2\).