ACO The ACO Seminar (2016–2017)

Oct. 6, 3:30pm, Wean 8220
Yury Sokolov, University of Pittsburgh
A modified bootstrap percolation on a random graph coupled with a lattice


Bootstrap percolation is an interactive particle system defined on a graph with a homogeneous local update rule. In k-neighbor bootstrap percolation, every vertex is in one of two possible states, active or inactive. Some vertices are initially activated. Active vertices stay so forever, and an inactive vertex becomes active whenever it has at least k active neighbors. During the last decades, bootstrap percolation has been extensively investigated on square lattices.

We introduce a random graph model G2N,pd, which is a combination of fixed torus grid edges in (ℤ/Nℤ)2 and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices u,v∈(ℤ/Nℤ)2 with graph distance d on the torus grid is pd=c/Nd, where c is some constant. In particular, we prove that, whp, the diameter D(G2N,pd)=Θ(log N). We consider a modified bootstrap percolation on G2N,pd, where the condition that an active vertex stays active forever is omitted. We derive critical probabilities for modified bootstrap percolation on the random graph in mean-field approximation.

Based on joint work with Svante Janson, Robert Kozma and Miklós Ruszinkó.

Back to the ACO home page