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

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=1ni=1ndid=\frac{1}{n}\sum_{i=1}^n d_i, let μ=d/(n1)\mu=d/(n-1), and let γ2=(n1)2i=1n(did)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

maxjdjd=o(nεmin{d,nd1}1/2),nmin{d,nd1},\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(n1)/2i(n1di).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.

Sources & referencesView supporting material

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.