Mixing time of random walk on the small-world network

Add to your list(s) Download to your calendar using vCal

• Andjela Sarkovic (Cambridge)
• Tuesday 28 October 2025, 14:00-15:00
• MR12.

If you have a question about this talk, please contact Perla Sousi.

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

This talk is part of the Probability series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.