The ACO Seminar (2016–2017)

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 G_ℤ²N,pd, which is a combination of fixed torus grid edges in (ℤ/Nℤ)² and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices u,v∈(ℤ/Nℤ)² with graph distance d on the torus grid is p_d=c/Nd, where c is some constant. In particular, we prove that, whp, the diameter D(G_ℤ²N,pd)=Θ(log N). We consider a modified bootstrap percolation on G_ℤ²N,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ó.