Description
In this talk a random graph model $G_{\mathbb{Z}2_N,p_d}$ will be 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}2_N,p_d})=\Theta (\log N)$. Moreover, we consider a modified non-monotonous bootstrap percolation on $G_{\mathbb{Z}2_N,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. This is a joint work with Svante Janson, Robert Kozma, Yury Sokolov.