Counting Hamilton cycles in sparse random directed graphs

Ferber A, Kwan MA, Sudakov B. 2018. Counting Hamilton cycles in sparse random directed graphs. Random Structures and Algorithms. 53(4), 592–603.


Journal Article | Published | English

Scopus indexed
Author
Ferber, Asaf; Kwan, Matthew AlanIST Austria; 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≥(logn+ω(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!(logn/n(1+o(1)))n directed Hamilton cycles.
Publishing Year
Date Published
2018-12-01
Journal Title
Random Structures and Algorithms
Volume
53
Issue
4
Page
592-603
ISSN
eISSN
IST-REx-ID

Cite this

Ferber A, Kwan MA, Sudakov B. Counting Hamilton cycles in sparse random directed graphs. Random Structures and Algorithms. 2018;53(4):592-603. doi:10.1002/rsa.20815
Ferber, A., Kwan, M. A., & Sudakov, B. (2018). Counting Hamilton cycles in sparse random directed graphs. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.20815
Ferber, Asaf, Matthew Alan Kwan, and Benny Sudakov. “Counting Hamilton Cycles in Sparse Random Directed Graphs.” Random Structures and Algorithms. Wiley, 2018. https://doi.org/10.1002/rsa.20815.
A. Ferber, M. A. Kwan, and B. Sudakov, “Counting Hamilton cycles in sparse random directed graphs,” Random Structures and Algorithms, vol. 53, no. 4. Wiley, pp. 592–603, 2018.
Ferber A, Kwan MA, Sudakov B. 2018. Counting Hamilton cycles in sparse random directed graphs. Random Structures and Algorithms. 53(4), 592–603.
Ferber, Asaf, et al. “Counting Hamilton Cycles in Sparse Random Directed Graphs.” Random Structures and Algorithms, vol. 53, no. 4, Wiley, 2018, pp. 592–603, doi:10.1002/rsa.20815.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1708.07746

Search this title in

Google Scholar