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 Grohe
Monday 25 June 2001
An error occured whilst processing this directive