A modified bootstrap percolation on a random graph coupled with a lattice

Abstract

In this paper a random graph model $G_{{\mathbb{Z}}_N^2,p_d}$ is introduced, which is a combination of fixed torus grid edges in $(\mathbb{Z}/N\mathbb{Z}{)}^2$ and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices $u,v\in (\mathbb{Z}/N\mathbb{Z}{)}^2$ with graph distance $d$ on the torus grid is $p_d=c/Nd$, where $c$ is some constant. We show that, {\em whp}, the diameter $D(G_{{\mathbb{Z}}_N^2,p_d})=\Theta (\log N)$. Moreover, we consider non-monotonous bootstrap percolation on $G_{{\mathbb{Z}}_N^2,p_d}$. We prove the presence of phase transitions in mean-field approximation and provide fairly sharp bounds on the error of the critical parameters. Our model addresses interesting mathematical questions of non-monotonous bootstrap percolation, and it is motivated by recent results of brain research.

The updated version includes several improvements, including the analysis of the process and its mean field approximation for a larger range of threshold values. Some open problems are added and the paper has a better readability

References in corpus (3)

• Mean-field driven first-order phase transitions in systems with long-range interactions
• Bootstrap percolation on a graph with random and local connections
• A sharp threshold for a modified bootstrap percolation with recovery

Cited by in corpus (1)

• Mean field dynamics of graphs I: Evolution of probabilistic cellular automata for random and small-world graphs