Efficient Hamilton covers and linear arboricity of random graphs

Abstract

A Hamilton cover of a graph is a collection of Hamilton cycles whose union contains all edges. Since each Hamilton cycle covers two edges at every vertex, every Hamilton cover has size at least $\lceil \hat{I}”(G)/2\rceil$. We prove that this lower bound is tight for binomial random graphs $G(n,p)$ throughout the widest possible range of edge probabilities: if $\ddot{I}‰(n)\to \infty$ and \[ \frac{\log n+\log\log n+ω(n)}{n} \le p=p(n) \le 1-\frac{ω(n)}{n^{2}}, \] then $G\sim G(n,p)$ with high probability has a Hamilton cover of size $\lceil \frac{\hat{I}”(G)}{2}\rceil .$ The main new contribution is the sparse regime near the Hamiltonicity threshold, where we prove a conjecture of Draganić, Glock, Munhá Correia and Sudakov. Our proof develops constructive tools for decomposing such graphs into controlled forest systems and extending them, using reserved pseudorandom structure, into Hamilton cycles. We also prove the corresponding hitting-time result for the random graph process, answering a question of Hefetz, Kühn, Lapinskas and Osthus. Finally, we use our methods to show that $G\sim G(n,p)$ with high probability satisfies the celebrated Linear arboricity conjecture for every $p\le 1$.

22 pages

Topics & keywords