Graph-versus-loopless-digraph degree-sequence conjecture
There exists an absolute constant such that, for every and every graphical degree sequence on vertices, writing , one has . Here is the number of simple graphs on vertex set with degree sequence , and is the number of loopless simple directed graphs on whose in-degree sequence and out-degree sequence are both .
References
Source: arXiv
Progress summary
A new unrefereed preprint narrows the gap substantially, but the conjecture remains unproved in the most general sparse and irregular cases.
The conjecture asks for a sharp comparison between the numbers of graphs and loopless directed graphs with a prescribed degree sequence, with consequences for random-graph approximation. The retrieved source does not identify its originator or date.
November 2026 progress
Behzad Mehrdad's preprint claims that the conjectured exponential loss can generally be reduced to an extra factor of . It claims the original inequality when the maximum-entropy edge probabilities remain uniformly separated from and , leaving the fully general sparse or irregular regime unresolved.
Current status (as of November 2026): The conjecture remains open in full generality; a preprint claims substantial partial progress, including the conjectured bound under a uniform nondegeneracy condition.
Sources
Solutions 0
No solutions have been posted yet.