2013/07/18 by Tobias Johnson, Johnson, Tobias, Elliot Paquette +1
Mathematics · #05C45 #05C80 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #Stochastic processes and statistical mechanics #math.CO #math.PR #msc:05C45 #msc:05C80 #msc:60C05
paper · pdf · doi:10.48550/arxiv.1307.4858
59 pages, 5 figures; minor changes for clarity
openalex publication_date 2013/07/18 · arxiv created 2015/05/22 · arxiv updated 2015/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We revisit the method of small subgraph conditioning, used to establish that random regular graphs are Hamiltonian a.a.s. We refine this method using new technical machinery for random d-regular graphs on n vertices that hold not just asymptotically, but for any values of d and n. This lets us estimate how quickly the probability of containing a Hamiltonian cycle converges to 1, and it produces quantitative contiguity results between different models of random regular graphs. These results hold with d held fixed or growing to infinity with n. As additional applications, we establish the distributional convergence of the number of Hamiltonian cycles when d grows slowly to infinity, and we prove that the number of Hamiltonian cycles can be approximately computed from the graph's eigenvalues for almost all regular graphs.