Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis

Abstract

In this paper we consider the existence of Hamilton cycles in the random graph $G=G_{n,m}^{\delta \ge 3}$. This a random graph chosen uniformly from 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 an earlier paper the second author showed that $c\ge 10$ is sufficient for this and in this paper we reduce the lower bound to $c>\mathrm{2.662...}$. This new lower bound is the same lower bound found in Frieze and Pittel \cite{FP} for the expansion of so-called Pósa sets.

arXiv admin note: text overlap with arXiv:1107.4947