Any fully graphic region of degree sequences can be sampled rapidly

Péter L. Erdős; Gábor Lippner; Na'ama Nevo; Lajos Soukup

paper

Any fully graphic region of degree sequences can be sampled rapidly

arXiv:2511.13564

Abstract

Let $n > c_{1} \geq c_{2}$ and $Σ$ be positive integers with $n \cdot c_{1} \geq Σ \geq n \cdot c_{2} .$ Let $\mD=\dds{n}Σ{c_1}{c_2}$ denote the set of all degree sequences of length $n$ with the even sum $Σ$ and satisfying $c_{1} \geq d_{i} \geq c_{2} .$ We show that if all degree sequences in $\mD$ are graphic, then $\mD$ is $3 n^{13}$ -stable. (The concept of $P$ -stability was introduced by Jerrum and Sinclair in 1990.) In particular, this implies that the switch Markov-chain mixes rapidly on all such degree sequences. In this paper we also study the inverse direction. We show the following: if all graphic sequences of a degree sequence region satisfy the $p (n)$ -stability condition then the overwhelming majority of the sequences in the region is graphic. This answers affirmatively a question raised in the paper \DOI{10.1016/j.aam.2024.102805}.

21 pages, 7 figures