Combinatorics Seminar

When: Sunday, January 13, 10am
Where: Schreiber 309
Speaker: Anita Liebenau, UNSW Sydney
Title: Enumerating graphs and other discrete structures by degree sequence

Abstract:

We show that the distribution of the degree sequence of $G(n,m)$ can be approximated by a sequence of n independent binomial variables $Bin(n-1,p)$ for a large range of $p$. This covers the range left open by previous work. In fact, we prove asymptotic formulae for the number of graphs of a given degree sequence, which implies the result about the degree sequence of the random graph. These formulae were conjectured in 1990 and 1997. In particular, we provide an asymptotic formula for the number of $d$-regular graphs for all $d$. The enumeration results are obtained via a new method of degree switching and "contraction" mappings. We apply similar methods to obtain asymptotic formulae for the number of bipartite graphs, digraphs and hypergraphs of a given degree sequence. In this talk I will present the new enumeration method and some of the consequences.

This is joint work with Nina Kamčev and Nick Wormald.