Premium
Counting Hamilton cycles in sparse random directed graphs
Author(s) -
Ferber Asaf,
Kwan Matthew,
Sudakov Benny
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20815
Subject(s) - combinatorics , mathematics , hamiltonian path , directed graph , random graph , directed acyclic graph , vertex (graph theory) , statement (logic) , discrete mathematics , feedback arc set , graph , line graph , voltage graph , political science , law
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 ) ) ) ndirected Hamilton cycles.