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

Let k3k\ge3 and 1dk21\le d\le k-2. For an nn-vertex kk-uniform hypergraph, let hd(k,n)=hdk1(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(nkd).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=k1d=k-1.

Sources & referencesView supporting material

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.