4
$\begingroup$

What is the best known asymptotic formula for the number of graphs with a given degree sequence $(d_1, ... ,d_n)$, when the degrees are bounded by a constant and the number of vertices $n$ goes to infinity?

There are several papers of Mckay et al that provide bounds when the degrees are all $O(n^{\frac{1}{2}})$, but I am interested in bounded degrees, and I was hoping for more exact bounds for this special case. There are works on this as well, but they all seem to be pretty old, so I was wondering what the current state of the art is.

|cite|improve this question
$\endgroup$
  • $\begingroup$ You can take the asymptotic formula for given degrees and sum it over all degrees within the bound. It isn't altogether trivial, but I'm pretty sure Nick Wormald did it somewhere. Sorry but I can't find it at the moment. $\endgroup$ – Brendan McKay Jul 11 '13 at 9:51
  • $\begingroup$ @BrendanMcKay doubtlessly knows more, but his paper arxiv.org/pdf/1303.4218v1.pdf with Catherine Greenhill seems very a propos... $\endgroup$ – Igor Rivin Jul 11 '13 at 13:54
  • $\begingroup$ Or maybe my memory was mistaken, since I was thinking of sciencedirect.com/science/article/pii/S0097316502000171 which has minimum degree not maximum degree. $\endgroup$ – Brendan McKay Jul 11 '13 at 16:08
3
$\begingroup$

In my comment I was misreading the question, sorry. The situation for the real question is as follows. For very low degrees (say, at most 3) it isn't hard to get the exact number as a single or double summation. For the more general case of bounded maximum degree, the best asymptotic formula is my result with Wormald (Combinatorica, 11 (1991) 369-382), which in this case has an error term $O(1/n)$ where $n$ is the number of vertices of non-zero degree. It would be possible (though somewhat tedious) to find an explicit bound on the error term, but as far as I know nobody has done it. It would also be possible (in this special case of bounded degree) to obtain the precise term of order $1/n$ and have an error term of size $O(1/n^2)$. But, again, I think nobody has done it.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.