Rainbow cycle error term in K_n

Status partial medium confidence

The open problem asks for the exact order of the error term $n - \ell^*(n)$, where $\ell^*(n)$ is the length of the longest rainbow cycle guaranteed in every properly edge-coloured $K_n$. Alon, Pokrovskiy, and Sudakov (2016, arXiv:1608.07028) established $\ell^*(n) \ge n - O(n^{3/4})$. Balogh and Molla (arXiv:1706.04950, published 2019) subsequently improved this to $\ell^*(n) \ge n - O(\log n \cdot \sqrt{n})$, so the deficit now lies between $\Omega(1)$ and $O(\log n \cdot \sqrt{n})$; the exact order remains open.

Cited literature (1)

• partial Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs (2019)
  J\u00f3zsef Balogh, Theodore Molla · European Journal of Combinatorics · arXiv:1706.04950

  Improves the error term for the longest rainbow cycle in any properly edge-coloured $K_n$ from $O(n^{3/4})$ to $O(\log n \cdot \sqrt{n})$.

Reviewer notes. Balogh-Molla 2019 (arXiv:1706.04950) improved the upper bound on the error term from $O(n^{3/4})$ to $O(\log n \cdot \sqrt{n})$, but the exact order remains unknown. A 2023 paper (arXiv:2309.04460, Alon-Buc\u0301ic\u0301-Sauermann-Zakharov-Zamir) achieves essentially tight bounds for rainbow cycles in sparse properly edge-coloured graphs, but does not directly resolve the deficit question for $K_n$. Andersen's Conjecture (rainbow path of length $n-2$) remains open and would imply a deficit of $O(1)$.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).