## 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}.

Original language | English (US) |
---|---|

Pages (from-to) | 17-51 |

Number of pages | 35 |

Journal | Combinatorics Probability and Computing |

Volume | 18 |

Issue number | 1-2 |

DOIs | |

State | Published - Mar 2009 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics