Rödl–Ruciński conjecture relating Hamilton cycles and perfect matchings

At least 10 years old · documented by

Let k≥3k\ge3 and 1≤d≤k−21\le d\le k-2. For an nn-vertex kk-uniform hypergraph, let hd(k,n)=hdk−1(k,n)h_d(k,n)=h_d^{k-1}(k,n) be the smallest integer such that minimum dd-degree at least hd(k,n)h_d(k,n) guarantees a Hamilton tight cycle, and let md(k,n)m_d(k,n) be the smallest integer such that minimum dd-degree at least md(k,n)m_d(k,n) guarantees a perfect matching. Rödl–Ruciński conjecture.

hd(k,n)=md(k,n)+o(nk−d).h_d(k,n)=m_d(k,n)+o(n^{k-d}).

This predicts that the asymptotic minimum dd-degree thresholds for Hamilton tight cycles and perfect matchings coincide. The source presents it as an open conjecture and discusses known results for the case d=k−1d=k-1.

References

Primary source

Jie Han and Yi Zhao, “Forbidding Hamilton cycles in uniform hypergraphs”, arXiv:1508.05623 (2015).

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.