Counting Hamilton cycles in sparse random directed graphs

Let D ( n , p )be the random directed graph on n vertices where each of the n ( n − 1 )possible arcs is present independently with probability p . A celebrated result of Frieze shows that if p ≥ ( log n + ω ( 1 ) ) / n then D ( n , p )typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in D ( n , p )is typically n !( p ( 1 + o ( 1 ) ) ) n . We also prove a hitting‐time version of this statement, showing that in the random directed graph process, as soon as every vertex has in‐/out‐degrees at least 1, there are typically n !( log n / n ( 1 + o ( 1 ) ) ) ndirected Hamilton cycles.