Nick Wormald

Asymptotic enumeration of sparse 2-connected graphs

ABSTRACT: We determine an asymptotic formula for the number of
2-connected graphs on $n$ vertices and $m$ edges, provided that
$m-n\to\infty$ and $m=O(n\log n)$ as $n\to\infty$. This is the
entire range of $m$ not covered by previous results. The proof
involves determining properties of the core and kernel of
random graphs with minimum degree at least 2. We also obtain
formulae for graphs with given degree sequence for most
(`typical') sequences. Our main result solves a problem of
Wright from 1983 and determines his mysterious constant $a$.
This is joint work with Graeme Kemkes and Cristiane Sato.
Another recent result will also be reported, filling the gap
for asymptotic enumeration of sparse strongly connected
digraphs. This is joint with Xavier Perez-Gimenez. An
underlying theme of the work reported here is one of avoiding
computations by defining appropriate probability spaces.


BIO: Nick Wormald is a Professor and Canada Research Chair in
the Department of Combinatorics and Optimization, University of
Waterloo. Among his Awards and Prizes: The 2006 Euler Medal of
the Institute for Combinatorics and its Applications, and the
1993 Australian Mathematical Society medal for research. He is
the Editor-in-Chief, Journal of Combinatorial Theory, Series B,
since 2004 and associate editor of a number of other journals.
He is well known as a leader in graph theory, enumeration of
combinatorial structures and probabilistic methods in
combinatorics, as well as applications to combinatorial
algorithms.