Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.13564 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908659604258816 |
|---|---|
| author | Erdős, Péter L. Lippner, Gábor Nevo, Na'ama Soukup, Lajos |
| author_facet | Erdős, Péter L. Lippner, Gábor Nevo, Na'ama Soukup, Lajos |
| contents | Let $n>c_1\ge c_2$ and $Σ$ be positive integers with $n\cdot c_1\ge Σ\ge 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\ge d_i\ge c_2.$ We show that if all degree sequences in $\mD$ are graphic, then $\mD$ is $3n^{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}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_13564 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Any fully graphic region of degree sequences can be sampled rapidly Erdős, Péter L. Lippner, Gábor Nevo, Na'ama Soukup, Lajos Combinatorics 05C07, 05C81, 60J10 Let $n>c_1\ge c_2$ and $Σ$ be positive integers with $n\cdot c_1\ge Σ\ge 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\ge d_i\ge c_2.$ We show that if all degree sequences in $\mD$ are graphic, then $\mD$ is $3n^{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}. |
| title | Any fully graphic region of degree sequences can be sampled rapidly |
| topic | Combinatorics 05C07, 05C81, 60J10 |
| url | https://arxiv.org/abs/2511.13564 |