Catherine Greenhill (University of New South Wales)

Friday 15th September, 12.05-12.55pm, Carslaw 373

Asymptotic enumeration of irregular bipartite graphs

The problem of obtaining an asymptotic formula for the number of 0-1 matrices with specified row and column sums has been well studied. Counting these matrices is equivalent to counting bipartite graphs with specified degrees. The total number of entries in the matrix equal to 1 (equivalently, edges in the graph) is the parameter which tends to infinity. In the sparse case, when all row and column sums are small, the combinatorial method of switchings can be applied. However, in the dense case completely different methods are used: the problem is reduced to the evaluation of a multidimensional complex integral. Intriguingly, in all known cases the answer can be written using the same formula involving binomial coefficients.

This is joint work with Rod Canfield, Brendan McKay and Xiaoji Wang.