Bootstrap percolation on Galton-Watson trees.(English)Zbl 1290.05058

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 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$$.

MSC:

 05C05 Trees 60K35 Interacting random processes; statistical mechanics type models; percolation theory 60C05 Combinatorial probability 60J80 Branching processes (Galton-Watson, birth-and-death, etc.) 05C80 Random graphs (graph-theoretic aspects)

Zbl 1102.60086
Full Text: