Mixing time of the swap Markov chain and P-stability

Abstract

The aim of this paper is to confirm that $P$-stability of a family of unconstrained/bipartite/directed degree sequences is sufficient for the swap Markov chain to be rapidly mixing on members of the family. This is a common generalization of every known result that shows the rapid mixing nature of the swap Markov chain on a region of degree sequences. In addition, for example, it encompasses power-law degree sequences with exponent $\gamma>2$, and, asymptotically almost surely, the degree sequence of any Erdős-Rényi random graph $G(n,p)$.
We also show that there exists a family of degree sequences which is not $P$-stable and its members have exponentially many realizations, yet the swap Markov chain is still rapidly mixing on them.