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 Δ(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 $ω(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 $\left\lceil \frac{Δ(G)}{2}\right\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\leq 1$.

Disclosure

“2 : it produces exactly ⌈∆(Gτ2 )/2⌉ linear forests covering all edges of Gτ2 , and then extends them to Hamilton cycles using the reserved random structure. This gives a tight Hamilton cover of Gτ2 whp. Acknowledgment. The authors used ChatGPT for language polishing, literature-search assist- ance, and informal discussion of minor auxiliary details. The main results and proofs are due to the authors. References [1] Miklós Ajtai, János Komlós, and Endre Szemerédi. The firs”

PDF page 20

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-23T18:55:46.973345Z

Structural counts