Details of talk
|Title||Counting d-regular graphs and the degree sequence of the random graph|
|Presenter||Anita Liebenau (Monash University)|
|Session||Algebra and Discrete Mathematics|
We do know exact formulae for some discrete structures. For example we know the number of graphs on $n$ vertices, or the number of trees on $n$ vertices. We struggle, however, to find exact formulae for the number of $d$-regular graphs on $n$ vertices. Even asymptotic formulae were known only for a limited range of $d$. We provide an asymptotic formula for the number of $d$-regular graphs for all $d$. In fact, we provide such a formula for the number of graphs of a given degree sequence. These formulae were conjectured in 1990 and 1997. The more general enumeration result is used to determine the distribution of the degree sequence of a graph that is drawn uniformly at random from all graphs on $n$ vertices and $m$ edges. This is joint work with Nick Wormald.