Summary: The switch chain is a well-studied Markov chain which can be used to sample approximately uniformly from the set \(\varOmega ( \mathfrak{d} )\) of all graphs with a given degree sequence \(\mathfrak{d} \). Polynomial mixing time (rapid mixing) has been established for the switch chain under various conditions on the degree sequences. G. Amanatidis and P. Kleer [in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 966–985 (2019; Zbl 1431.60073)] introduced the notion of strongly stable families of degree sequences, and proved that the switch chain is rapidly mixing for any degree sequence from a strongly stable family. Using a different approach, P. L. Erdős et al. [“The mixing time of the switch Markov chains: a unified approach”, Preprint, arXiv:1903.06600] recently extended this result to the (possibly larger) class of P-stable degree sequences, introduced by M. Jerrum et al. [in: Random graphs. Volume 2. Based on papers presented at the fourth international seminar on random graphs and probabilistic methods in combinatorics, held in Poznań, Poland, August 7-11, 1989. Chichester: Wiley. 101–115 (1992; Zbl 0819.05052)]. We define a new notion of stability for a given degree sequence, namely \(k\)-stability, and prove that if a degree sequence \(\mathfrak{d}\) is 8-stable then the switch chain on \(\varOmega ( \mathfrak{d} )\) is rapidly mixing. We also provide sufficient conditions for P-stability, strong stability and 8-stability. Using these sufficient conditions, we give the first proof of P-stability for various families of heavy-tailed degree sequences, including power-law degree sequences, and show that the switch chain is rapidly mixing for these families.
We further extend these notions and results to directed degree sequences.