THE TIME OF BOOTSTRAP PERCOLATION WITH DENSE INITIAL SETS

• 成果类型: Article
• 署名作者: Bollobas, Bela; Holmgren, Cecilia; Smith, Paul; Uzzell, Andrew J.
• 署名单位: University of Cambridge; University of Memphis
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/12-AOP818
• 发表日期: 2014
• 页码: 1337-1373
• 关键词: sharp metastability threshold; Poisson approximation; rates

摘要

Let r is an element of N. In r-neighbour bootstrap percolation on the vertex set of a graph G, vertices are initially infected independently with some probability p. At each time step, the infected set expands by infecting all uninfected vertices that have at least r infected neighbours. When p is close to 1, we study the distribution of the time at which all vertices become infected. Given t = t (n) = o (log n/ log log n), we prove a sharp threshold result for the probability that percolation occurs by time t in d-neighbour bootstrap percolation on the d-dimensional discrete torus T. Moreover, we show that for certain ranges of p = p(n), the time at which percolation occurs is concentrated either on a single value or on two consecutive values. We also prove corresponding results for the modified d-neighbour rule.