Short monochromatic odd cycles

Abstract 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ő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ão and Hunter obtained the first nontrivial upper bound by showing that $L(k)=O({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.