Estimate $f(n)$: the shortest monochromatic odd cycle forced in $n$-colourings of $K_{2^n+1}$ (Erdős #609)
Statement
For an integer $n\geq 1$, let $f(n)$ be the least $m$ with the following property: in every colouring of the edges of the complete graph $K_{2^n+1}$ with $n$ colours there is a monochromatic odd cycle of length at most $m$. (Such an $m$ exists because $2^n+1$ vertices in $n$ colours force a monochromatic odd cycle.) Estimate the growth rate of $f(n)$ as $n\to\infty$.
Acceptance. FULLY RESOLVES: determine the asymptotic growth of $f(n)$ — matching upper and lower bounds of the same order (e.g. $f(n)=2^{(1/2+o(1))n}$, or another form) — with complete proofs of both directions. ADVANCES: improve the best known upper bound (currently $f(n)\ll n^{3/2}2^{n/2}$ [JaYi25]) or the best known lower bound (currently $f(n)\geq 2^{c\sqrt{\log n}}$ [DaJo17]), strictly beyond the bounds stated in the background, with proof — an improved upper bound may be delivered as an explicit colouring construction plus a proof that it avoids all monochromatic odd cycles shorter than the claimed length; OR compute $f(n)$ exactly for a new small value of $n$ via exhaustive/SAT search over $n$-colourings of $K_{2^n+1}$, with a reproducible certificate (an explicit optimal colouring together with a proof/certificate that no colouring avoids all odd cycles up to $f(n)-1$). Deliver the asymptotic proof, the improved bound with proof, or the search code plus certified colouring/value.
Background
A problem of Erdős and Graham [ErGr75]; listed as open on erdosproblems.com/609 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). The vertex count $2^n+1$ is sharp: the edges of $K_{2^n}$ can be $n$-coloured so as to avoid monochromatic odd cycles of ANY length (an iterated bipartite-doubling construction), and it can be shown that even at $2^n+1$ vertices the short cycles $C_5$ and $C_7$ can be avoided for large $n$, so $f(n)$ genuinely grows. Chung [Ch97] asked whether $f(n)\to\infty$; Day and Johnson [DaJo17] proved that it does, and gave the lower bound $$f(n)\geq 2^{c\sqrt{\log n}}$$ for some constant $c>0$. The trivial upper bound is $f(n)\leq 2^n$. On the upper side, Girão and Hunter [GiHu24] proved $f(n)\ll 2^n/n^{1-o(1)}$, subsequently improved by Janzer and Yip [JaYi25] to $$f(n)\ll n^{3/2}\,2^{n/2}.$$ Thus the current frontier is a wide gap between the lower bound $2^{c\sqrt{\log n}}$ and the upper bound $n^{3/2}2^{n/2}$. Erdős offered no cash prize. The attacker's tool: on the upper side, explicit $n$-colourings of $K_{2^n+1}$ (found by SAT / algebraic / local-search construction) that avoid short monochromatic odd cycles give record upper bounds and, for small $n$, exact values of $f(n)$; on the lower side, extremal/counting arguments bounding how short a monochromatic odd cycle must appear.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #609 (T. F. Bloom) | website |
| REF-02 | Erdős graphs problem collection — colourings without small monochromatic odd cycles | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.