On the Number of Hamilton Cycles in Pseudo-Random Graphs

Michael Krivelevich


We prove that if $G$ is an $(n,d,\lambda)$-graph (a $d$-regular graph on $n$ vertices, all of whose non-trivial eigenvalues are at most $\lambda)$ and the following conditions are satisfied:

  1. $\frac{d}{\lambda}\ge (\log n)^{1+\epsilon}$ for some constant $\epsilon>0$;
  2. $\log d\cdot \log\frac{d}{\lambda}\gg \log n$,

then the number of Hamilton cycles in $G$ is $n!\left(\frac{d}{n}\right)^n(1+o(1))^n$.

Full Text: