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.

arXiv commentThe 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 (7)

• Statistical mechanics of complex networks
• Scaling and percolation in the small-world network model
• The phase transition in inhomogeneous random graphs
• Bootstrap percolation on the random graph $G_{n,p}$
• 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