# 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.

##### MSC:
 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:
##### References:
  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  H. Garmo, Random railways and cycles in random regular graphs, Ph.D. Thesis, Uppsala University, Sweden, 1998. · Zbl 0904.60010  Janson, S.; łuczak, T.; Ruciński, A.: Random graphs. (2000) · Zbl 0968.05003  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  J. McCammond, D. Wise, Locally convex small cancellation groups, preprint, 2001.  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  Robinson, R. W.; Wormald, N. C.: Existence of long cycles in random cubic graphs. Enumeration and design, 251-270 (1984) · Zbl 0566.05040  Robinson, R. W.; Wormald, N. C.: Almost all cubic graphs are Hamiltonian. Random structures algorithms 3, 117-125 (1992) · Zbl 0755.05075  Robinson, R. W.; Wormald, N. C.: Almost all regular graphs are Hamiltonian. Random structures algorithms 5, 363-374 (1994) · Zbl 0795.05088  Wormald, N. C.: Differential equations for random processes and random graphs. Ann. appl. Probab. 5, 1217-1235 (1995) · Zbl 0847.05084  Wormald, N. C.: Models of random regular graphs. Lecture notes in mathematical science, lecture note series 267, 239-298 (1999) · Zbl 0935.05080  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.