Optimal covers of random graphs with Hamilton cycles

5 March 2013
Dan Hefetz
We prove that if $\frac{\log^{117} n}{n} \leq p \leq 1 - n^{-1/8}$, then asymptotically almost surely the edges of $G(n,p)$ can be covered by $\lceil \Delta(G(n,p))/2 \rceil$ Hamilton cycles. This is clearly best possible and improves an approximate result of Glebov, Krivelevich and Szab\'o, which holds for $p \geq n^{-1 + \varepsilon}$. Based on joint work with Daniela Kuhn, John Lapinskas and Deryk Osthus.
  • Combinatorial Theory Seminar