Packing conjecture for type-ll Hamilton cycles

About 10 years old · traced to

Let k>l≥2k>l\ge 2. A random kk-uniform hypergraph Hn,pkH^k_{n,p} has vertex set of size nn, and a type-ll Hamilton cycle is a Hamilton cycle whose consecutive edges overlap in ll vertices. Here whp⁡\operatorname{whp} means with high probability as n→∞n\to\infty, and o(1)o(1) denotes a quantity tending to zero.

Packing conjecture. There exists a constant CC such that, if (k−l)∣n(k-l)\mid n and

p≥log⁡Cnnk−l,p \geq \frac{\log^{C} n}{n^{k-l}},

then, with high probability, Hn,pkH^k_{n,p} contains

(nk)pn/(k−l)(1+o(1))\frac{{n \choose k}p}{n/(k-l)}(1+o(1))

edge-disjoint type-ll Hamilton cycles.

The preceding result establishes the analogous assertion for loose Hamilton cycles, corresponding to l=1l=1, up to a polylogarithmic factor. The authors explain that their proof does not extend to l≥2l\geq 2 because the edge exposure used to close paths becomes polynomially wasteful; obtaining this packing result for larger overlap types is posed as an interesting direction.

References

Primary source

Asaf Ferber, Kyle Luh, Daniel Montealegre and Oanh Nguyen, “Packing Loose Hamilton Cycles”, arXiv:1608.01278 (2016).

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.