Percolation Model On Sparse Graphs With O(1)-eigenvalue Separation

Let G be a graph, Ot(?)V(G) be a vertex subset of G, it is the set of all the active vertices until time t. Let (G, p,|O0|) denote the dynamic discrete percolation process starting with the initial active vertex set O0and transition probability p at each time. The process stops the first time Ot=V(G). The percolation time t(G,p, O0) is the least T with OT=V(G) if such a T exists or oo otherwise. Additionally, let (?)(G) denote the normalized Laplacian of a graph G, and let denote the eigenvalues of (?)(G). We say that G has o(1)-eigenvalue separation if In this paper, we show that for any real number (?)∈(0,1). there exists a finite T such that a.a.s for any graph G of order n with minimum degree at least n(?) and o(1)-eigenvalue separation, the percolation time t(G,p, O0)≤T even for|I0|=1.