Further Information
How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence?
Asymptotic formulae for the first question are known when d=o(\sqrt(n)) and when d= \Omega(n). More generally, asymptotic formulae are known for
the number of graphs with a given degree sequence, for a range of degree sequences that is wide enough to deduce asymptotic formulae for the second
question for p =o(1/o(\sqrt(n))) and p = Theta(1).
McKay and Wormald showed that the formulae for the sparse case and the
dense case can be cast into a common form, and then conjectured in 1990 and 1997 that the same formulae should hold for the gap range. A particular consequence of both conjectures is that the degree sequence of the random graph G(n,p) can be approximated by a sequence of n independent
binomial variables Bin(n − 1, p').
In 2017, Nick Wormald and I proved both conjectures. In this talk I will describe the problem and survey some of the earlier methods to showcase the differences to our new methods. I shall also report on enumeration results of other discrete structures, such as bipartite graphs and hypergraphs, that are obtained by adjusting our methods to those settings.