For how many edges is a digraph almost certainly Hamiltonian?

Abstract:

${K_n}(r)$ is the number of those Hamiltonian cycles in the complete digraph on $n$ nodes, each of which has just $r$ edges in common with a particular Hamiltonian cycle, and $B(n,r) = n!/\{ r!(n - r)!\}$. We show that ${K_n}(r) = B(n,r){K_{n - r}}(0)$ and deduce that ${K_n}(0)\sim (n - 1)!{e^{ - 1}}$ for large $n$ and that ${K_n}(r)\sim (n - 1)!{e^{ - 1}}/r!$ if $r = 0(n)$. An $(n,q)$ digraph is one with $n$ labelled nodes and $q$ edges. From the result for ${K_n}(r)$, we deduce that, if $q{n^{ - 3/2}} \to \infty$ as $n \to \infty$, then almost all $(n,q)$ digraphs are Hamiltonian. If $q{n^{ - 3/2}} \to c$ as $n \to \infty$, then the proportion of $(n,q)$ digraphs which are non-Hamiltonian is at most $1 - \exp ( - {c^{ - 2}})$ as $n \to \infty$.