Packing and counting arbitrary Hamilton cycles in random digraphs

2019 
We prove packing and counting theorems for arbitrarily oriented Hamilton cycles in ${\cal D}(n,p)$ for nearly optimal $p$ (up to a $\log ^cn$ factor). In particular, we show that given $t = (1-o(1))np$ Hamilton cycles $C_1,\ldots ,C_{t}$, each of which is oriented arbitrarily, a digraph $D \sim {\cal D}(n,p)$ w.h.p. contains edge disjoint copies of $C_1,\ldots ,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 {\cal D}(n,p)$ w.h.p. contains $(1\pm o(1))n!p^n$ copies of $C$, provided $p \geq \log ^{1 + o(1)}n/n$.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    23
    References
    3
    Citations
    NaN
    KQI
    []