← All problems

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

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}.
References

Status

  • Solved: Anita Liebenau and Nick Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph (Journal of the European Mathematical Society, 2023) https://doi.org/10.4171/jems/1355

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.