zbMATH — the first resource for mathematics

Hamiltonian decompositions of random bipartite regular graphs. (English) Zbl 1033.05082
Summary: We prove a complete Hamiltonian decomposition theorem for random bipartite regular graphs, thereby verifying a conjecture of Robinson and Wormald. The main step is to prove contiguity (a kind of asymptotic equivalence) of two probabilistic models of 4-regular bipartite graphs; namely, the uniform model, and the model obtained by taking the union of two independent, uniformly chosen bipartite Hamilton cycles, conditioned on forming no multiple edges. The proof uses the small subgraph conditioning method to establish contiguity, while the differential equation method is used to analyse a critical quantity.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C80 Random graphs (graph-theoretic aspects)
05C45 Eulerian and Hamiltonian graphs
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
Full Text: DOI
[1] Frieze, A.; Jerrum, M.; Molloy, M.; Robinson, R.; Wormald, N.: Generating and counting Hamilton cycles in random regular graphs. J of algorithms 21, 176-198 (1996) · Zbl 0857.68084
[2] H. Garmo, Random railways and cycles in random regular graphs, Ph.D. Thesis, Uppsala University, Sweden, 1998. · Zbl 0904.60010
[3] Janson, S.; łuczak, T.; Ruciński, A.: Random graphs. (2000) · Zbl 0968.05003
[4] Kim, J. H.; Wormald, N. C.: Random matchings which induce Hamilton cycles, and Hamiltonian decompositions of random regular graphs. J. combin. Theory ser. B 81, 20-44 (2001) · Zbl 1030.05107
[5] J. McCammond, D. Wise, Locally convex small cancellation groups, preprint, 2001.
[6] Molloy, M. S. O.; Robalewska, H.; Robinson, R. W.; Wormald, N. C.: 1-factorisations of random regular graphs. Random structures algorithms 10, 305-321 (1997) · Zbl 0974.05062
[7] Robinson, R. W.; Wormald, N. C.: Existence of long cycles in random cubic graphs. Enumeration and design, 251-270 (1984) · Zbl 0566.05040
[8] Robinson, R. W.; Wormald, N. C.: Almost all cubic graphs are Hamiltonian. Random structures algorithms 3, 117-125 (1992) · Zbl 0755.05075
[9] Robinson, R. W.; Wormald, N. C.: Almost all regular graphs are Hamiltonian. Random structures algorithms 5, 363-374 (1994) · Zbl 0795.05088
[10] Wormald, N. C.: Differential equations for random processes and random graphs. Ann. appl. Probab. 5, 1217-1235 (1995) · Zbl 0847.05084
[11] Wormald, N. C.: Models of random regular graphs. Lecture notes in mathematical science, lecture note series 267, 239-298 (1999) · Zbl 0935.05080
[12] Wormald, N. C.: The differential equation method for random graph processes and greedy algorithms. Lectures on approximation and randomized algorithms, 73-155 (1999) · Zbl 0943.05073
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.