Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1017/S0963548308009322 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
log log n,infected vertex,stronger bound,majority bootstrap percolation,graph g,following deterministic rule,probability p,log log log n,critical probability,vertex v | Log-log plot,Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Bootstrap percolation,Torus,Percolation,Hypercube,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
18 | 1-2 | 0963-5483 |
Citations | PageRank | References |
19 | 2.60 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Béla Bollobás | 2 | 2696 | 474.16 |
| Robert Morris | 3 | 101 | 13.12 |