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

Abstract

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.