OPEN
Let $f(n)$ be the minimal $m$ such that if the edges of $K_{2^n+1}$ are coloured with $n$ colours then there must be a monochromatic odd cycle of length at most $m$. Estimate $f(n)$.
A problem of Erdős and Graham. The edges of $K_{2^n}$ can be $n$-coloured to avoid odd cycles of any length. It can be shown that $C_5$ and $C_7$ can be avoided for large $n$.
Chung [Ch97] asked whether $f(n)\to \infty$ as $n\to \infty$. Day and Johnson [DaJo17] proved this is true, and that
\[f(n)\geq 2^{c\sqrt{\log n}}\]
for some constant $c>0$. The trivial upper bound is $2^n$.
Girão and Hunter [GiHu24] have proved that
\[f(n) \ll \frac{2^n}{n^{1-o(1)}}.\]
See also the entry in the graphs problem collection.
