The time of bootstrap percolation with dense initial sets for all thresholds
| Autor: | Andrew J. Uzzell, Béla Bollobás, Paul Smith |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Percolation critical exponents Concentration of measure Applied Mathematics General Mathematics media_common.quotation_subject Percolation threshold Torus Function (mathematics) Infinity Computer Graphics and Computer-Aided Design Combinatorics Percolation Continuum percolation theory Software media_common Mathematics |
| Zdroj: | Random Structures & Algorithms. 47:1-29 |
| ISSN: | 1042-9832 |
| DOI: | 10.1002/rsa.20529 |
| Popis: | We study the percolation time of the r-neighbour bootstrap percolation model on the discrete torus i¾?/ni¾?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 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text