Counting Hamilton cycles in sparse random directed graphs. Issue 4 (18th October 2018)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Kwan, Matthew; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 53:Issue 4(2018)
• Page Start: 592
• Page End: 603
• Publication Date: 2018-10-18
• Subjects: Directed graph -- hamilton cycle -- random graph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20815
• Languages: English
• ISSNs: 1042-9832

Abstract

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.