Hamilton cycles in random graphs with minimum degree at least 3: An improved analysis. Issue 4 (16th October 2020) - Anastos, Michael; Frieze, Alan
Abstract : In this paper we consider the existence of Hamilton cycles in the random graph G = G n, m δ ≥ 3 . This random graph is chosen uniformly from 𝒢 n, m δ ≥ 3, the set of graphs with vertex set [ n ], m edges and minimum degree at least 3. Our ultimate goal is to prove that if m = cn and c > 3/2 is constant then G is Hamiltonian w.h.p. In Frieze (2014), the second author showed that c ≥ 10 is sufficient for this and in this paper we reduce the lower bound to c > 2.662…. This new lower bound is the same lower bound found in Frieze and Pittel (2013) for the expansion of so‐called Pósa sets.