The time of bootstrap percolation with dense initial sets

DOI10.1214/12-AOP818MaRDI QIDQ400563zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Cecilia Holmgren, Andrew J. Uzzell, Paul Smith

Publication date 22 August 2014

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.3922

bootstrap percolation Poisson convergence result Stein-Chen method

Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: 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. We study the distribution of the time t 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_n^d. 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.

Review text

The percolation model in the title reads as follows. The process is the spin system on a vertex set \(V\) of a graph \(G,\) with each vertex \(v\) having two possible states labeled as ``infected and ``uninfected. Let \(A_t\) be the set of infected vertices at time \(t\geq 0\). Then NEWLINE\[NEWLINEA_{t+1}=A_t\cup \{v:| N(v)\bigcap A_t| \geq r\},\tag{1}NEWLINE\]NEWLINE where \(N(v)\) is the neighborhood of \(v\). (1) says that in the \(r\)-neighbor percolation process considered, an infected vertex remains infected if it has at least \(r\) infected neighbors. Starting with the initial state \(A_0=A\), it is said that \(A\) percolates if \( A_t=V(G)\) for some \(t.\) Accordingly, the percolation time \(T\) is defined to be \(T:=T(G,A)=\min\{t:A_t=V(G)\}.\)NEWLINENEWLINEThe paper is devoted to the study of \(T\) under the following two common assumptions:NEWLINENEWLINE(i) the graph \(G\) is the \(d\)-dimensional torus \({\mathcal T}^d_n\) with vertex set \(({\mathcal Z}/n{\mathcal Z}^d);\) (ii) the initial state \(A\) is a random subset of \({\mathcal T}^d_n\), such that infected vertices are chosen from \(A\) independently with probability \(p\in (0,1)\).NEWLINENEWLINEThe authors' main result establishes a sharp threshold for the percolation time \(T({\mathcal T}^d_n,A), \) namely, it states that with high probability \(T=T({\mathcal T}^d_n,A)\in [t,t+1]\) for \(t=o(\log n/\log\log n)\). The main ingredient of the proof is the following Poisson convergence result, stemming from the Stein method. Let \(E_t(x)\) denote the event that a vertex \(x\) is uninfected at time \(t\) and let \(F_t(x)\) be the indicator of the random variable \(E_t(x)\). Consider the induced sequence of random variables \(\bar{F}_t(n):=\sum_{x\in V({\mathcal T}_n^d)} F_t(x)\). Then, for a sequence of probabilities \(p_n\) such that \( 1-p_n\leq Cn^{-d/m_t},\) where \(m_t\) is the number of vertices with \(l_1\) norm at most \(t,\) and for \(t=o(\log n/\log\log n),\) NEWLINE\[NEWLINEd_{TV}\Big( \bar{F}_t(n), Po(n^d \mathbb P_{p_n}(E_t(x))\Big)=o(1).NEWLINE\]

Recommendations

Cites work

Cited in

(12)

This page was built for publication: The time of bootstrap percolation with dense initial sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q400563)