Packing conjecture for type-ll Hamilton cycles

Let k>l2k>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 nn\to\infty, and o(1)o(1) denotes a quantity tending to zero.

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

plogCnnkl,p \geq \frac{\log^{C} n}{n^{k-l}},

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

(nk)pn/(kl)(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 l2l\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.

Sources & referencesView supporting material

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.