Log-log factor in rainbow-cycle bounds

Question 10.1 · arXiv:2309.04460

arXiv Question high confidence— first stated 2025-02-26

Authors: Noga Alon, Matija Bucić, Lisa Sauermann, Dmitrii Zakharov, Or Zamir

Status open high confidence

Question 10.1 asks whether the $\log\log n$ factor in the average-degree bound of Theorem 1.1 is necessary to guarantee a rainbow cycle in a properly edge-coloured graph. The May 2026 literature review found no follow-up resolving the question.

Reviewer notes. The exact statement was verified in Section 10 of the cached arXiv v2 HTML. The earlier review incorrectly reported that the HTML ended before Section 10.

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

Question. Is the $\log\log n$ factor in the bound for the average degree in Theorem 1.1 necessary in order to guarantee a rainbow cycle?

Context

Appears in Section 10 of the paper, which collects open questions remaining after the main results on rainbow cycles and the connections to additive number theory for non-abelian groups.

Source paper

Essentially tight bounds for rainbow cycles in proper edge-colourings
Noga Alon, Matija Bucić, Lisa Sauermann, Dmitrii Zakharov, Or Zamir · 2025-02-26
https://arxiv.org/abs/2309.04460