Register for: WIMSIG2017

Details of talk

TitleCounting d-regular graphs and the degree sequence of the random graph
PresenterAnita Liebenau (Monash University)
Author(s)Anita Liebenau
SessionAlgebra and Discrete Mathematics
Time11:00:00 2017-09-25

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.