Bootstrap percolation on infinite trees and non-amenable groups

Details Bootstrap percolation on infinite trees and non-amenable groups Bootstrap percolation on infinite trees and non-amenable groups

2003-11-08

arxiv.org/abs/math/0311125v3

Combinatorics, Probability and Computing 15 (2006), no. 5, 715-730

Mathematics

Probability

17 pages, 2 figures. This is the final version, for the journal Combinatorics, Probability and Computing. Proposition 1.5 is n

Scientific paper

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 neighbors at a certain time step, then it becomes occupied in the next step. This process is well-studied on Z^d; 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 general 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') \leq \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.

Affiliated with

Also associated with

No associations

Rating

Bootstrap percolation on infinite trees and non-amenable groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bootstrap percolation on infinite trees and non-amenable groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bootstrap percolation on infinite trees and non-amenable groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-604097