Short monochromatic odd cycles

It is easy to see that every k -edge-colouring of the complete graph on 2ᵏ+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 K2ᵏ+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¹⁻ᵒ⁽¹⁾)) , which improves the trivial bound by a polynomial factor. We obtain an exponential improvement by proving that L(k)=O(k3/22k/2) . Our proof combines tools from algebraic combinatorics and approximation theory.