Majority Bootstrap Percolation on the Hypercube

Source abstract

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. We say that percolation occurs if eventually every vertex is infected. The elements of the set of initially infected vertices, A ⊂ 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 [17] 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 → ∞. In this paper we study the case when the growth of d to ∞ is not excessively slow; in particular, we show that the critical probability is 1/2 + o (1) if d ≥ (log log n ) 2 log log log n , and give much stronger bounds in the case that G is the hypercube, [2] d .