Covering random digraphs with Hamilton cycles

Source abstract

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 \geq p \geq \frac{\log^{20} n}{n}$$ 1 / 2 ≥ p ≥ 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 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.