The Log-Log Factor for Rainbow Cycles

Definitions and mathematical statement

A proper edge coloring of a graph $G=(V,E)$ is a map $\chi:E\to\mathcal C$, where $\mathcal C$ is a set of colors, such that edges sharing a vertex have different colors. A rainbow cycle is a cycle whose edges have pairwise distinct colors. For a finite graph with $n=|V|$ vertices, its average degree is $\overline d(G)=2|E|/n$.

The supplied record asks whether the factor $\log\log n$ is necessary in an average-degree bound of order $\log n\log\log n$ that forces a rainbow cycle in a properly edge-colored graph. Its original wording refers to "Theorem 1", whose full statement and hypotheses are not supplied. In particular, the graph conventions are not explicitly specified. The following precise formulations are conditional on the intended graphs being finite, simple, and undirected; here cycles have length at least three, and logarithms are natural.

For integers $n\ge3$, define \[ f(n)=\max\left\{\frac{2|E(G)|}{n}: |V(G)|=n,\ G\text{ is finite, simple, and undirected, and admits a proper edge coloring with no rainbow cycle}\right\}. \] A precise question about removing the factor entirely is whether \[ f(n)=O(\log n)\qquad(n\to\infty). \] Equivalently, does there exist a constant $C>0$ and an integer $n_0\ge3$ such that, for every integer $n\ge n_0$, every $n$-vertex graph in this class and every proper edge coloring of it contain a rainbow cycle whenever \[ \overline d(G)\ge C\log n? \] A stronger interpretation of necessity of the full factor asks instead whether there exists $c>0$ such that, for infinitely many integers $n\ge3$, some graph in this class admits a proper edge coloring with no rainbow cycle and satisfies \[ \overline d(G)\ge c\log n\log\log n. \] These interpretations are distinct: failure of an $O(\log n)$ bound need not establish necessity of the full $\log\log n$ factor. The supplied excerpt does not specify which interpretation is intended. Its dated curation reports an $O(\log n\log\log n)$ sufficient bound and labels the question open; these are supplied source assessments, not independently verified mathematical or literature conclusions.

Short English statement

The question asks whether the extra $\log\log n$ in the stated average-degree guarantee for a rainbow cycle can be removed. The source does not supply the referenced theorem's full hypotheses or distinguish complete removal of the factor from proving that the full factor is necessary. The displayed formulations therefore require review against that theorem.

Sources

• Local UnsolvedMath registry: supplied complete record for permanent ID $30006158$, source problem code catalogue entry, title The Log-Log Factor for Rainbow Cycles, in the Oberwolfach Reports Open Problems collection. The supplied record labels the problem open and its statement corrected_verified; the accompanying verification says only formula delimiters, notation, grammar, and typography were repaired. These labels are source metadata, not independent verification. No individual proposer is supplied; the proposed year is 2025.
• Graph Theory (2025), Oberwolfach Reports, DOI 10.4171/owr/2025/1, pp. 5--74. Supplied report provenance: mathematical workshop discussions and open problems. https://doi.org/10.4171/owr/2025/1. The original excerpt refers to "Theorem 1" without supplying its full statement or a precise location within the report.
• Alon--Bucić--Sauermann--Zakharov--Zamir, as attributed in the supplied literature sources: https://arxiv.org/abs/2309.04460. No paper title or theorem number is supplied for this reference.
• Supplied literature assessment dated 2026-08-22: it labels the question open, describes an $O(\log n\log\log n)$ average-degree sufficient bound as the best current theorem, describes the remaining precision gap as the $\log\log n$ factor, and says the authors explicitly leave its necessity open. The listed sources checked are the preceding arXiv reference and Oberwolfach Report 1/2025. This assessment is supplied dated curation derived from the OWR record, not independently verified; its time-sensitive status and cited claims require independent checking.