Majority bootstrap percolation on the hypercube
| dc.creator | Balogh, József | |
| dc.creator | Bollobás, Béla | |
| dc.creator | Morris, Robert | |
| dc.date | 2007-02-13 | |
| dc.date.accessioned | 2026-07-07T07:46:41Z | |
| dc.date.available | 2026-07-07T07:46:41Z | |
| dc.description | 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. | |
| dc.description | 44 pgs, no figures, submitted Feb 2007 | |
| dc.identifier | https://arxiv.org/abs/math/0702373 | |
| dc.identifier | http://arxiv.org/abs/math/0702373 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/123909 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.title | Majority bootstrap percolation on the hypercube | |
| dc.type | text |