Conjecture on near-optimal Hamilton coverings of random graphs

Let G(n,p)G(n,p) be the binomial random graph on nn vertices, and let a Hamilton covering be a collection of Hamilton cycles whose union contains every edge of G(n,p)G(n,p). Here p=p(n)p=p(n) may depend on nn, and p=ω(lnn/n)p=\omega(\ln n/n) means that pn/lnnp n/\ln n\to\infty.

Hamilton covering conjecture. For any p=ω(lnn)/np=\omega(\ln n)/n, the random graph G(n,p)G(n,p) a.a.s. admits a covering of its edges with at most

(1+o(1))np2(1+o(1))\frac{np}{2}

Hamilton cycles.

This would extend the paper's asymptotic equality between the largest Hamilton packing and smallest Hamilton covering to the full range where the random graph's minimum and maximum degrees are asymptotically equal. The authors state that the stronger lower bound used in their proof is likely only a proof artifact, and that this claim should hold whenever p=ω(lnn)/np=\omega(\ln n)/n; no resolution is given.

Sources & referencesView supporting material

Primary source

Roman Glebov, Michael Krivelevich and Tibor Szabó, “On covering expander graphs by Hamilton cycles”, arXiv:1111.3325 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.