Optimal covers of random graphs with Hamilton cycles

Optimal covers of random graphs with Hamilton cycles

Tue, 05/03
14:30 		Dan Hefetz (Birmingham) Combinatorial Theory Seminar Add to calendar L3
Optimal covers of random graphs with Hamilton cycles
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ó, which holds for $ p \geq n^{-1 + \varepsilon} $. Based on joint work with Daniela Kuhn, John Lapinskas and Deryk Osthus.