Fang's multipartite cycle conjecture

At least 5 years old · documented by

Let r≥3r\ge 3 and let n1≥n2≥⋯≥nr≥1n_{1}\ge n_{2}\ge \cdots\ge n_{r}\ge 1. Let Kn1,n2,…,nrK_{n_{1},n_{2},\ldots,n_{r}} be the complete rr-partite graph with parts of these sizes, let GG be a subgraph of it, and let f(n1,n2,…,nr)f(n_{1},n_{2},\ldots,n_{r}) be the edge threshold defined by Fang, Győri, Li and Xiao. A multipartite cycle is a cycle in which no two consecutive vertices lie in the same part. Fang's multipartite cycle conjecture. If

e(G)≥f(n1,n2,…,nr)+1,e(G)\ge f(n_{1},n_{2},\ldots,n_{r})+1,

then GG contains a multipartite cycle of length at most 32r\frac{3}{2}r. The conjecture proposes a general threshold for forcing short multipartite cycles in complete multipartite graphs; the supplied text does not state whether it has been resolved.

References

Primary source

Chunqiu Fang, Ervin Győri, Chuanqi Xiao and Jimeng Xiao, “Turán numbers and anti-Ramsey numbers for short cycles in complete 3-partite graphs”, arXiv:2011.13715 (2020).

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.