McKay–Wormald's asymptotic enumeration conjecture for graphs with given degree sequence

About 9 years old · traced to

Let d=(d1,…,dn){\bf d}= (d_1,\ldots,d_n) be a degree sequence, let g(d)g({\bf d}) denote the number of graphs with degree sequence d{\bf d}, let d=1n∑i=1ndid=\frac{1}{n}\sum_{i=1}^n d_i, let μ=d/(n−1)\mu=d/(n-1), and let γ2=(n−1)−2∑i=1n(di−d)2\gamma_2=(n-1)^{-2}\sum_{i=1}^n(d_i-d)^2. McKay–Wormald's conjecture. For some absolute constant ε>0\varepsilon>0, if d=d(n){\bf d}={\bf d}(n) satisfies

max⁡j∣dj−d∣=o(nεmin⁡{d,n−d−1}1/2),nmin⁡{d,n−d−1}→∞,\max_j|d_j-d|=o\left(n^\varepsilon\min\{d,n-d-1\}^{1/2}\right),\qquad n\min\{d,n-d-1\}\to\infty,

and ∑idi\sum_i d_i is even, then

g(d)∼2exp⁡(14−γ224μ2(1−μ)2)(μμ(1−μ)1−μ)n(n−1)/2∏i(n−1di).g({\bf d})\sim \sqrt{2}\exp\left(\frac14-\frac{\gamma_2^2}{4\mu^2(1-\mu)^2}\right)\left(\mu^\mu(1-\mu)^{1-\mu}\right)^{n(n-1)/2}\prod_i\binom{n-1}{d_i}.

This conjecture unifies asymptotic formulae known in sparse and dense ranges and extends them to the intermediate range for degree sequences sufficiently close to regular; the paper proves the conjecture, so the enumeration formula is now established under these hypotheses.

References

Primary source

Anita Liebenau and Nick Wormald, “Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph”, arXiv:1702.08373 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.