Mixing time of the swap Markov chain and P-stability


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)$ where $p$ is bounded away from 0 and 1 by at least $\frac{5\log n}{n-1}$. 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.

Bratislava, Slovakia

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