Abstract | ||
---|---|---|
We study the percolation time of the r-neighbour bootstrap percolation model on the discrete torus ﾿/n﾿d. For t at most a polylog function of n and initial infection probabilities within certain ranges depending on t, we prove that the percolation time of a random subset of the torus is exactly equal to t with high probability as n tends to infinity. Our proof rests crucially on three new extremal theorems that together establish an almost complete understanding of the geometric behaviour of the r-neighbour bootstrap process in the dense setting. The special case d-r=0 of our result was proved recently by Bollobas, Holmgren, Smith and Uzzell. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 1-29, 2015 |
Year | DOI | Venue |
---|---|---|
2015 | 10.1002/rsa.20529 | Random Structures & Algorithms |
Keywords | Field | DocType |
concentration of measure | Discrete mathematics,Combinatorics,Concentration of measure,Percolation critical exponents,Infinity,Torus,Percolation threshold,Percolation,Continuum percolation theory,Bootstrapping (electronics),Mathematics | Journal |
Volume | Issue | ISSN |
47 | 1 | 1042-9832 |
Citations | PageRank | References |
3 | 0.56 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bela Bollobas | 1 | 66 | 12.05 |
Paul Smith | 2 | 9 | 1.21 |
Andrew J. Uzzell | 3 | 13 | 4.48 |