Minimum Degree Edge-Disjoint Hamilton Cycles in Random Directed Graphs

In this paper we consider the problem of finding "as many edge-disjoint Hamilton cycles as possible" in the binomial random digraph Dn,p. We show that a typical Dn,p contains precisely the minimum between the minimum out-and in-degrees many edge-disjoint Hamilton cycles, given that p ⩾ log 15 n/n, which is optimal up to a factor of polylog n. Our proof provides a randomized algorithm to generate the cycles and uses a novel idea of generating Dn,p in a sophisticated way that enables us to control some key properties, and on an "online sprinkling" idea as was introduced by Ferber and Vu.