P-stable degree sequence regions for bipartite and directed graphs
Abstract
The switch Markov chain is a natural method for sampling graph realizations with a prescribed degree sequence, and P-stability is a general sufficient condition for its rapid mixing. Since P-stability is often difficult to verify directly, we develop an approach based on the simpler and more readily verifiable property of \emph{full graphicality}. We consider bidegree sequence regions obtained by fixing the two class sizes, the common degree sum, and lower and upper bounds for the degrees in each class. Such a region is fully graphic if every bidegree sequence satisfying these constraints has a bipartite realization. Our main result shows that every fully graphic region of this form is P-stable. More precisely, for class sizes n and m, the perturbation ratio is at most (nm)5. It follows from a known theory that the switch Markov chain is rapidly mixing on every such region. We also show that full graphicality can be tested on a canonical extremal bidegree sequence and use this characterization to derive several new explicit sufficient conditions. By encoding loopless directed graphs as bipartite graphs, we develop a parallel theory for directed degree sequences. This gives analogous extremal characterizations, sufficient conditions for full graphicality, and P-stability and rapid-mixing results for directed degree-sequence regions. The encoding process allows most corresponding statements for the two cases to be formulated and proved in one run.
Related
- Local versus global average degree in bipartite graphs
- Classification of bipartite observables I: stable and uniformly stable observables
- Dominant-Degree Conditions for Ramsey--Turán Factors of Non-Directed Cycle Orientations
- Degree sequence condition for pancyclicity in tough graphs
- The realization graph of every degree sequence has a Hamilton path
BibTeX
@misc{erdos2026pstable,
title = {{P-stable degree sequence regions for bipartite and directed graphs}},
author = {Péter L. Erdős and Gábor Lippner and Na'ama Nevo and Lajos Soukup},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35777},
eprint = {2610.35777},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35777},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - P-stable degree sequence regions for bipartite and directed graphs
AU - Péter L. Erdős
AU - Gábor Lippner
AU - Na'ama Nevo
AU - Lajos Soukup
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35777
UR - https://arxiv.org/abs/2610.35777
AB - The switch Markov chain is a natural method for sampling graph realizations with a prescribed degree sequence, and P-stability is a general sufficient condition for its rapid mixing. Since P-stability is often difficult to verify directly, we develop an approach based on the simpler and more readily verifiable property of \emph{full graphicality}. We consider bidegree sequence regions obtained by fixing the two class sizes, the common degree sum, and lower and upper bounds for the degrees in each class. Such a region is fully graphic if every bidegree sequence satisfying these constraints has a bipartite realization. Our main result shows that every fully graphic region of this form is P-stable. More precisely, for class sizes n and m, the perturbation ratio is at most (nm)^5. It follows from a known theory that the switch Markov chain is rapidly mixing on every such region. We also show that full graphicality can be tested on a canonical extremal bidegree sequence and use this characterization to derive several new explicit sufficient conditions. By encoding loopless directed graphs as bipartite graphs, we develop a parallel theory for directed degree sequences. This gives analogous extremal characterizations, sufficient conditions for full graphicality, and P-stability and rapid-mixing results for directed degree-sequence regions. The encoding process allows most corresponding statements for the two cases to be formulated and proved in one run.
ER -