Paperlane

no. 3 · Tuesday 27 October 2026

P-stable degree sequence regions for bipartite and directed graphs

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

math.CO · 29 pp

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.

comments
29 pages, 6 figures
fields
Combinatorics
pdf ↗ page arXiv:2610.35777 ↗