Logo
All Random Solved Random Open
SOLVED
Let $f(n)$ be minimal 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)$. Does $f(n)\to \infty$ as $n\to \infty$?
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$.

Day and Johnson [DaJo17] have shown that \[f(n)\geq 2^{c\sqrt{\log n}}\] for some constant $c>0$.

See also the entry in the graphs problem collection.

Additional thanks to: Zach Hunter