Packing and counting arbitrary Hamilton cycles in random digraphs

Abstract

We prove packing and counting theorems for arbitrarily oriented Hamilton cycles in $\mathcal{D}(n,p)$ for nearly optimal $p$ (up to a ${\log }^{c}n$ factor). In particular, we show that given $t=(1-o(1))np$ Hamilton cycles $C_1,\dots ,C_t$, each of which is oriented arbitrarily, a digraph $D\sim \mathcal{D}(n,p)$ w.h.p. contains edge disjoint copies of $C_1,\dots ,C_t$, provided $p=\omega ({\log }^{3}n/n)$. We also show that given an arbitrarily oriented $n$-vertex cycle $C$, a random digraph $D\sim \mathcal{D}(n,p)$ w.h.p. contains $(1\pm o(1))n!p^n$ copies of $C$, provided $p\ge {\log }^{1+o(1)}n/n$.

13 pages