Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.02191
curl -X POST /api/v1/records/arxiv/2611.02191/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.02191/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'