A non-$P$-stable class of degree sequences for which the swap Markov chain is rapidly mixing

Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei, István Miklós, Dániel Soltész

Published 2019-09-05Version 1

One of the simplest methods of generating a random graph with a given degree sequence is provided by the Monte Carlo Markov Chain method using swaps. The swap Markov chain converges to the uniform distribution, but generally it is not known whether this convergence is rapid or not. After a number of results concerning various degree sequences, rapid mixing was established for so-called $P$-stable degree sequences (including that of directed graphs), which covers every previously known rapidly mixing region of degree sequences. In this paper we give a non-trivial family of degree sequences that are not $P$-stable and the swap Markov chain is still rapidly mixing on them. The proof uses the 'canonical paths' method of Jerrum and Sinclair. The limitations of our proof are not fully explored.