Majority bootstrap percolation on the hypercube

Details Majority bootstrap percolation on the hypercube Majority bootstrap percolation on the hypercube

2007-02-13

arxiv.org/abs/math/0702373v1

Mathematics

Combinatorics

44 pgs, no figures, submitted Feb 2007

Scientific paper

In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected, then v is also infected, and infected vertices remain infected forever. Percolation occurs if eventually every vertex is infected. The elements of the set of initially infected vertices, A \subset V(G), are normally chosen independently at random, each with probability p, say. This process has been extensively studied on the sequence of torus graphs [n]^d, for n = 1,2,..., where d = d(n) is either fixed or a very slowly growing function of n. For example, Cerf and Manzo showed that the critical probability is o(1) if d(n) < log*(n), i.e., if p = p(n) is bounded away from zero then the probability of percolation on [n]^d tends to one as n goes to infinity. In this paper we study the case when the growth of d to infinity is not excessively slow; in particular, we show that the critical probability is 1/2 + o(1) if d > (loglog(n))^2 logloglog(n), and give much stronger bounds in the case that G is the hypercube, [2]^d.

Affiliated with

Also associated with

No associations

Rating

Majority bootstrap percolation on the hypercube 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 Majority bootstrap percolation on the hypercube, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Majority bootstrap percolation on the hypercube will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-409800