The time of bootstrap percolation with dense initial sets (Q400563)

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\]