Answers are grounded in this paper and cite their sources.
Bootstrap percolation on an arbitrary graph has a random initial configuration, where each vertex is occupied with probability p , independently of each other, and a deterministic spreading rule with a fixed parameter k : if a vacant site has at least k occupied neighbours at a certain time step, then it becomes occupied in the next step. This process is well studied on Zᵈ ; here we investigate it on regular and general infinite trees and on non-amenable Cayley graphs. The critical probability is the infimum of those values of p for which the process achieves complete occupation with positive probability. On trees we find the following discontinuity: if the branching number of a tree is strictly smaller than k , then the critical probability is 1, while it is $1-1/k$ on the k -ary tree. A related result is that in any rooted tree T there is a way of erasing k children of the root, together with all their descendants, and repeating this for all remaining children, and so on, such that the remaining tree $T'$ has branching number br(T')≤ max\ br(T)-k,\,0\ . We also prove that on any $2k$ -regular non-amenable graph, the critical probability for the k -rule is strictly positive.
No takes yet. Share an insight, caveat, or question.
Balogh et al. (2006) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: