Date: Thursday September 20 at 2pm.

Venue: Room 67-341.

Title: Hamiltonian decompositions of random bipartite regular graphs.

Speaker: Catherine Greenhill, Melbourne University

Abstract: Robinson and Wormald conjectured in 1994 that a randomly chosen bipartite d-regular graph could asymptotically almost surely be decomposed into the edge-disjoint union of Hamilton cycles and at most one perfect matching. (Here "asymptotically almost surely" means "with probability tending to 1 as n tends to infinity", where n is the number of vertices in the graph.) We have proved this conjecture by establishing contiguity, a kind of asymptotic equivalence, of various probabilistic models of bipartite regular graphs. The small subgraph conditioning method is used to establish contiguity, while the differential equations method is used to calculate a critical quantity.

I will describe this result and give a flavour of the proof. All necessary terms will be defined.

Joint work with Jeong Han Kim and Nicholas C Wormald.

This page maintained by Nicholas Cavenagh, Department of Mathematics, University of Queensland.