1Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary 2School of Mathematics and Statistics, UNSW Sydney, Australia
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 659-665
Citer cet article
Péter L. Erdős; Catherine S. Greenhill; Tamás Róbert Mezei; István Miklós; Dániel Soltész; Lajos Soukup; Péter L. Erdős; Catherine S. Greenhill; Tamás Róbert Mezei; István Miklós; Dániel Soltész; Lajos Soukup. Mixing time of the swap Markov chain and P-stability. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 659-665. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a46/
@article{AMUC_2019_88_3_a46,
author = {P\'eter L. Erd\H{o}s and Catherine S. Greenhill and Tam\'as R\'obert Mezei and Istv\'an Mikl\'os and D\'aniel Solt\'esz and Lajos Soukup and P\'eter L. Erd\H{o}s and Catherine S. Greenhill and Tam\'as R\'obert Mezei and Istv\'an Mikl\'os and D\'aniel Solt\'esz and Lajos Soukup},
title = { Mixing time of the swap {Markov} chain and {P-stability}},
journal = {Acta mathematica Universitatis Comenianae},
pages = {659--665},
year = {2019},
volume = {88},
number = {3},
url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a46/}
}
TY - JOUR
AU - Péter L. Erdős
AU - Catherine S. Greenhill
AU - Tamás Róbert Mezei
AU - István Miklós
AU - Dániel Soltész
AU - Lajos Soukup
AU - Péter L. Erdős
AU - Catherine S. Greenhill
AU - Tamás Róbert Mezei
AU - István Miklós
AU - Dániel Soltész
AU - Lajos Soukup
TI - Mixing time of the swap Markov chain and P-stability
JO - Acta mathematica Universitatis Comenianae
PY - 2019
SP - 659
EP - 665
VL - 88
IS - 3
UR - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a46/
ID - AMUC_2019_88_3_a46
ER -
%0 Journal Article
%A Péter L. Erdős
%A Catherine S. Greenhill
%A Tamás Róbert Mezei
%A István Miklós
%A Dániel Soltész
%A Lajos Soukup
%A Péter L. Erdős
%A Catherine S. Greenhill
%A Tamás Róbert Mezei
%A István Miklós
%A Dániel Soltész
%A Lajos Soukup
%T Mixing time of the swap Markov chain and P-stability
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 659-665
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a46/
%F AMUC_2019_88_3_a46
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.
