Personal tools
You are here: Home Events Abstract Archives 2001 Hamiltonian decomposition of random bipartite regular graphs

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 Grohe


Monday 25 June 2001
Document Actions