Hamilton cycles in random graphs with minimum degree at least 3: An improved analysis. Issue 4 (16th October 2020)

• Record Type: Journal Article
• Authors: Anastos, Michael; Frieze, Alan
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 865
• Page End: 878
• Publication Date: 2020-10-16
• Subjects: 3‐core -- Hamilton cycle -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20978
• Languages: English
• ISSNs: 1042-9832

Abstract

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.