Covering Random Digraphs with Hamilton Cycles

Abstract

A covering of a digraph $D$ by Hamilton cycles is a collection of directed Hamilton cycles (not necessarily edge-disjoint) that together cover all the edges of $D$. We prove that for $1/2\ge p\ge \frac{{\log }^{20}n}{n}$, the random digraph $D_{n,p}$ typically admits an optimal Hamilton cycle covering. Specifically, the edges of $D_{n,p}$ can be covered by a family of $t$ Hamilton cycles, where $t$ is the maximum of the the in-degree and out-degree of the vertices in $D_{n,p}$. Notably, $t$ is the best possible bound, and our assumption on $p$ is optimal up to a polylogarithmic factor.