On the mixing time of switch Markov chains

Alfréd Rényi Insitute of Mathematics

Generating graphs with a given degree sequence uniformly and randomly is a challenging problem. One of the popular methods is the switch Markov chain, which is a Markov chain Monte Carlo method that takes a random walk on the set of realizations via switches. A switch operation takes two disjoint edges $ab$ and $cd$ in the graph, and replaces them with $ad$ and $bc$ if those are not already there, thus it preserves the degree sequence. It is conjectured that the switch Markov chain rapidly converges to the uniform distribution for any degree sequence.

As the main result, I will present a theorem which removes most of the technical difficulties from proving rapid mixing of the switch Markov chain on the realizations of so-called $P$-stable degree sequences.

Based on joint works with PL Erdős, C Greenhill, E Győri, I Miklós, D Soltész, L Soukup.


My research interests include Graph Theory, Computational Geometry, and Algorithms