Multipartite Dirac conjecture for Hamiltonicity

For each integer r4r\geq 4, let KrK_r be the complete graph on rr parts, let Cr\mathcal{C}_r denote the collection of Hamilton cycles on rr labelled vertices, and let πKr(Cr)\pi_{K_r}(\mathcal{C}_r) be the rr-partite density threshold for Hamiltonicity.

Multipartite Dirac conjecture. The Hamiltonicity threshold should converge to 12\frac{1}{2} as rr\rightarrow\infty:

limrπKr(Cr)=12.\lim_{r\rightarrow\infty} \pi_{K_r}(\mathcal{C}_r)=\frac{1}{2}.

A theorem in the paper gives a lower bound strictly greater than 1/21/2 for every fixed r4r\geq 4, while the conjecture predicts that these thresholds nevertheless approach 1/21/2 asymptotically.

Sources & referencesView supporting material

Primary source

Leila Badakhshian, Victor Falgas-Ravry and Maryam Sharifzadeh, “On density conditions for transversal trees in multipartite graphs”, arXiv:2305.05713 (2023).

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.