Presented on September 21, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116W.
Finally, our small-world network has been studied by @cite_19 in the special case @math . However, the results of @cite_19 are about bootstrap percolation, rather than being about the mixing time of the lazy random walk, which is our concern here.
@cite_19
2903855202
Abstract In this paper a random graph model G Z N 2 , p d is introduced, which is a combination of fixed torus grid edges in ( Z ∕ N 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 ∈ ( Z ∕ N Z ) 2 with graph distance d on the torus grid is p d = c ∕ N d , where c is some constant. We show that, whp, the diameter D ( G Z N 2 , p d ) = Θ ( log N ) . Moreover, we consider a modified non-monotonous bootstrap percolation on G 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.