Counting Hamilton cycles in sparse random directed graphs. Issue 4 (18th October 2018) - Ferber, Asaf; Kwan, Matthew; Sudakov, Benny
Abstract: 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 ) ) ) n directed Hamilton cycles.