Short monochromatic odd cycles

2025/06/17 by Janzer, Oliver, Yip, Fredy · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2506.14910

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(\frac2^kk^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/22^k/2). Our proof combines tools from algebraic combinatorics and approximation theory.

Citations

• Monochromatic odd cycles in edge-coloured complete graphs
• Upper bounds for multicolour Ramsey numbers
• The asymptotics of r(4,t)
• An exponential improvement for diagonal Ramsey
• Lower bounds for multicolor Ramsey numbers
• Exact Ramsey numbers of odd cycles via nonlinear optimisation
• Multicolour Ramsey Numbers of Odd Cycles

Cited by

• An improved upper bound for the multicolour Ramsey number of odd cycles

Related

• Monochromatic odd cycles in edge-coloured complete graphs
• Multicolour Ramsey Numbers of Odd Cycles
• A note on multicolor Ramsey number of small odd cycles versus a large clique
• Circumference, Chromatic Number and Online Coloring
• Long monochromatic even cycles in 3-edge-coloured graphs of large\n minimum degree