Problem Statement
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)$.
Categories:
Graph Theory Ramsey Theory
Progress
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)}}.\]Janzer and Yip [JaYi25] have improved this to\[f(n) \ll n^{3/2}2^{n/2}.\]See also the entry in the graphs problem collection.
Source: erdosproblems.com/609 | Last verified: January 15, 2026