Abstract
| 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. |