← All problems

Graph-versus-loopless-digraph degree-sequence conjecture

There exists an absolute constant C>0C>0 such that, for every n≥1n\ge 1 and every graphical degree sequence d=(d1,…,dn)d=(d_1,\ldots,d_n) on nn vertices, writing M=12∑i=1ndiM=\frac{1}{2}\sum_{i=1}^n d_i, one has G(d)≥D(d)exp⁡ ⁣(−Cnlog⁡ ⁣(2+Mn))G(d)\ge \sqrt{D(d)}\exp\!\left(-C n\log\!\left(2+\frac{M}{n}\right)\right). Here G(d)G(d) is the number of simple graphs on vertex set [n][n] with degree sequence dd, and D(d)D(d) is the number of loopless simple directed graphs on [n][n] whose in-degree sequence and out-degree sequence are both dd.

References

Progress summary

Refreshed
Open · progress reported

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 log⁡n\log n. It claims the original inequality when the maximum-entropy edge probabilities remain uniformly separated from 00 and 11, 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.