On the Number of Hamilton Cycles in Sparse Random Graphs

Authors:
  • RGRoman Glebov
    Roman Glebov
  • MKMichael Krivelevich
    Michael Krivelevich

Abstract
We prove that the number of Hamilton cycles in the random graph $G(n,p)$ is $n!p^n(1+o(1))^n$ asymptotically almost surely (a.a.s.), provided that $p\geq \frac{\ln n+\ln\ln n+\omega(1)}{n}$. Furthermore, we prove the hitting time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree $2$ creates $(\frac{\ln n}{e})^n(1+o(1))^n$ Hamilton cycles a.a.s.

This publication has 25 references indexed in Scilit: