# Hamiltonian decomposition of random bipartite regular graphs

Catherine Greenhill Department of Mathematics and Statistics University of Melbourne 4pm Thursday 28 June 2001 Room 2511, JCMB, King's Buildings

A random *d*-regular graph on *n* vertices a.a.s. has an
edge-decomposition into Hamilton cycles, when *d* is an even
constant. (Here a.a.s. means `asymptotically almost surely';
i.e. with probability tending to 1 as *n* tends to infinity).
Kim and Wormald proved this using the *small subgraph
conditioning method*. Recently, Kim, Wormald and I proved the
corresponding result for random *bipartite* regular graphs,
using the same method. Perhaps surprisingly, the result is
harder to prove for bipartite graphs. Two critical quantities
needed for the proof are analysed using the *differential
equations method*.

(Joint work with Jeong Han Kim and Nick Wormald.)

Martin GroheMonday 25 June 2001