It is easy to see that every $k$-edge-colouring of the complete graph on $2^k+1$ vertices contains a monochromatic odd cycle. In 1973, Erd\H{ o}s and Graham asked to estimate the smallest $L(k)$ such that every $k$-edge-colouring of $K_{ 2^k+1}$ contains a monochromatic odd cycle of length at most $L(k)$. Recently, Gir\~ao and Hunter obtained the first nontrivial upper bound by showing that $L(k)=O(\frac{ 2^k}{ k^{ 1-o(1)}})$, which improves the trivial bound by a polynomial factor. We obtain an exponential improvement by proving that $L(k)=O(k^{ 3/2}2^{ k/2})$. Our proof combines tools from algebraic combinatorics and approximation theory.
Categories: math.CO