Mixing time of the swap Markov chain and P-stability

Main Article Content

Péter L. Erdős Catherine S. Greenhill Tamás Róbert Mezei István Miklós Dániel Soltész Lajos Soukup


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.

Article Details

How to Cite
Erdős, P., Greenhill, C., Mezei, T., Miklós, I., Soltész, D., & Soukup, L. (2019). Mixing time of the swap Markov chain and P-stability. Acta Mathematica Universitatis Comenianae, 88(3), 659-665. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1228/770