Abstract

Recently, there has been an increasing interest in studying mixing properties of random walks on random graphs that have an underlying structure and some smaller random perturbation. In this talk, we will consider a ‘small-world network model’ introduced by Dyer et al, which is meant to resemble real-world networks with an underlying spatial structure and random connections whose probability decays with distance. We start with a d-dimensional torus of side length n, and for each pair (x,y) of different vertices, we add an edge between them with probability Z/|x-y|^d independently, where Z is chosen such that the expected number of added edges is 1 for each vertex. We study a simple random walk on this random graph in at least 3 dimensions, and we show that with high probability, its mixing time is of order log n, and there is no cutoff.

Joint work with Zsuzsanna Baran, Jonathan Hermon, Allan Sly and Perla Sousi