Asymptotic enumeration of regular graphs

145 Views Asked by At

I have been following a few papers on the asymptotic enumeration of $r$-regular graphs of $n$ vertices, $L_r$.

According to Random Graphs, $L_r = L_n \sim \sqrt{2} e^{- \frac{\left(r^2 - 1\right)}{4}} \left(\frac{r^{\frac{r}{2} e^{-\frac{r}{2}}}}{r!}\right)^n n^{\frac{r n}{2}}$.

According to Asymptotic enumeration by degree sequence of graphs with degrees $o(n^{1/2})$, $L_r = \frac{\left(n k\right)!}{\left(\frac{nk}{2}\right)! 2^{\frac{nk}{2}} \left(k !\right)^n} e^{\left(-\frac{k^2 -1}{4} - \frac{k^3}{12 n} + O \left(\frac{k^2}{n}\right)\right)}$ where $r = o\left(n^{\frac{1}{2}}\right)$.

According to ASYMPTOTIC ENUMERATION BY DEGREE SEQUENCE OF GRAPHS OF HIGH DEGREE, $L_r = \sqrt{2} \left(2 \pi n \lambda^{d+1} \left(1 - \lambda\right)^{n-d}\right)^{-\frac{n}{2}} e^{\left(\frac{-1 + 10 \lambda -10\lambda^2}{12 \lambda \left(1 - \lambda\right)} + O\left(n^{-\zeta}\right)\right)}$

Which one should I use?

1

There are 1 best solutions below

0
On BEST ANSWER

The first formula is the one you want to use.

A $r$-regular graph is a specific case of a graph over a fixed degree sequence. Now with some assumptions on the degree sequence, you can get a formula enumerating the number of graphs over that sequence. And in particular, when the graph is $r$-regular the degree sequence has a nice form which simplifies to the first expression you gave. Brendan McKay's papers are concerned with relaxing the assumptions made on the degree sequence, which obviously complexifies the matter.