2023/10/17 by Draganić, Nemanja, Glock, Stefan, Correia, David Munhá +1 · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2310.11580
In his seminal 1976 paper, Pósa showed that for all p≥ Clog n/n, the binomial random graph G(n,p) is with high probability Hamiltonian. This leads to the following natural questions, which have been extensively studied: How well is it typically possible to cover all edges of G(n,p) with Hamilton cycles? How many cycles are necessary? In this paper we show that for p≥ Clog n/n, we can cover G∼ G(n,p) with precisely \lceilΔ(G)/2\rceil Hamilton cycles. Our result is clearly best possible both in terms of the number of required cycles, and the asymptotics of the edge probability p, since it starts working at the weak threshold needed for Hamiltonicity. This resolves a problem of Glebov, Krivelevich and Szabó, and improves upon previous work of Hefetz, Kühn, Lapinskas and Osthus, and of Ferber, Kronenberg and Long, essentially closing a long line of research on Hamiltonian packing and covering problems in random graphs.