Short monochromatic odd cycles

Abstract It is easy to see that every k -edge-colouring of the complete graph on 2 Superscript k Baseline plus 1 2 k + 1 $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 upper K Subscript 2 Sub Superscript k Subscript plus 1 K 2 k + 1 $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 upper L left parenthesis k right parenthesis equals upper O left parenthesis 2 Superscript k Baseline divided by left parenthesis k Superscript 1 minus o left parenthesis 1 right parenthesis Baseline right parenthesis right parenthesis L ( k ) = O ( 2 k / ( k 1 − o ( 1 ) ) ) $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 upper L left parenthesis k right parenthesis equals upper O left parenthesis k Superscript 3 divided by 2 Baseline 2 Superscript k divided by 2 Baseline right parenthesis L ( k ) = O ( k 3 / 2 2 k / 2 ) $L(k)=O(k^{3/2}2^{k/2})$ . Our proof combines tools from algebraic combinatorics and approximation theory.