Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density
Abstract
For a degree sequence d on n vertices with M edges, let G(d) be the number of simple graphs and D(d) the number of loopless digraphs with in-degree = out-degree = d. We conjecture that G(d) >= sqrt(D(d)) exp(-C n log(2+M/n)) for every graphical d, a single inequality across all densities, and prove it up to an extra factor log n: G(d) >= sqrt(D(d)) exp(-C n log n log(2+M/n)) for every graphical d. The proof compares pairs of graphs with Eulerian digraphs by alternately colouring closed trails; the failure of injectivity is measured exactly, shared edges cancel against 2-cycles, and parity is handled by merging trails and by a parity argument on Eulerian circuits of odd components. No asymptotic enumeration and no bound on the maximum-entropy multipliers is used. When the maximum-entropy edge probabilities lie in [delta, 1-delta], the same method gives the conjecture itself, G(d) >= sqrt(D(d)) exp(-C n log n / delta). Combined with the exact identity G(d) = exp(g*(d)) pi(d), where pi(d) is the probability that the maximum-entropy beta-model has degrees exactly d, and a van der Waerden-type bound for D(d), this shows that uniformly random graphs with degree sequence d are close in the normalized cut metric to their beta-model whenever M >> n log n log(M/n), at every density, with no tameness and no cap on the degrees. We also record the conjecture in the sparse regime and, with constant 1/2+o(1), in the dense tame regime, from the asymptotic enumerations of McKay-Wormald and Barvinok-Hartigan.
Related
- Domains of Monomial Convergence in Banach Sequence Spaces
- Whole-Sequence Convergence of Variable-Smoothing Full-Splitting Methods via a Lifted Kurdyka-Łojasiewicz Framework
- The semiclassical limit from Hartree to Vlasov at positive density: strong uniform-in-time convergence and scattering
- A Shadow Sequence Technique for Last-Iterate Convergence Analysis of the Random Reshuffling Method: Relaxed Stepsize Conditions and Beyond
- Global existence and convergence of a density heat flow for strictly subcritical Liouville systems
BibTeX
@misc{mehrdad2026graphs,
title = {{Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density}},
author = {Behzad Mehrdad},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02191},
eprint = {2611.02191},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02191},
}
RIS
TY - UNPB
TI - Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density
AU - Behzad Mehrdad
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.02191
UR - https://arxiv.org/abs/2611.02191
AB - For a degree sequence d on n vertices with M edges, let G(d) be the number of simple graphs and D(d) the number of loopless digraphs with in-degree = out-degree = d. We conjecture that G(d) >= sqrt(D(d)) exp(-C n log(2+M/n)) for every graphical d, a single inequality across all densities, and prove it up to an extra factor log n: G(d) >= sqrt(D(d)) exp(-C n log n log(2+M/n)) for every graphical d. The proof compares pairs of graphs with Eulerian digraphs by alternately colouring closed trails; the failure of injectivity is measured exactly, shared edges cancel against 2-cycles, and parity is handled by merging trails and by a parity argument on Eulerian circuits of odd components. No asymptotic enumeration and no bound on the maximum-entropy multipliers is used. When the maximum-entropy edge probabilities lie in [delta, 1-delta], the same method gives the conjecture itself, G(d) >= sqrt(D(d)) exp(-C n log n / delta). Combined with the exact identity G(d) = exp(g*(d)) pi(d), where pi(d) is the probability that the maximum-entropy beta-model has degrees exactly d, and a van der Waerden-type bound for D(d), this shows that uniformly random graphs with degree sequence d are close in the normalized cut metric to their beta-model whenever M >> n log n log(M/n), at every density, with no tameness and no cap on the degrees. We also record the conjecture in the sparse regime and, with constant 1/2+o(1), in the dense tame regime, from the asymptotic enumerations of McKay-Wormald and Barvinok-Hartigan.
ER -