Multicolour Ramsey of odd cycles negligible vs triangles: $R_k(C_{2n+1})/R_k(K_3)\to0$ (Erdős #554)
Statement
For a graph $G$, let $R_k(G)$ denote the $k$-colour Ramsey number: the least $m$ such that every colouring of the edges of $K_m$ with $k$ colours contains a monochromatic copy of $G$. Prove that for every fixed integer $n\geq 2$, $$\lim_{k\to\infty}\frac{R_k(C_{2n+1})}{R_k(K_3)}=0,$$ where $C_{2n+1}$ is the cycle on $2n+1$ vertices and $K_3$ is the triangle. The problem is open already for $n=2$ (the pentagon $C_5$).
Acceptance. FULLY RESOLVES: a complete proof — machine-checkable (Lean/Coq) preferred, else a full written proof — that $\lim_{k\to\infty} R_k(C_{2n+1})/R_k(K_3)=0$ for every fixed $n\geq 2$; equivalently that $R_k(C_{2n+1})=o(R_k(K_3))$ as $k\to\infty$. ADVANCES: improve the best-known upper bound on $R_k(C_{2n+1})$ (currently $(4n-2)^k k^{k/n}+1$, [ACJMR25]) or the best lower bound on $R_k(K_3)$ (currently $\gg C^k$) in a way that provably narrows the ratio, stating the new bound and confirming it is strictly better than the one in the background; OR settle the first open case $n=2$ ($C_5$ versus $K_3$); OR prove the limit conditionally on Erdős's conjecture $R_k(K_3)\leq C^k$, with the conditional hypothesis clearly flagged. Deliver the proof file.
Background
A problem of Erdős and Graham [Er81c]; listed as open on erdosproblems.com/554 (fetched 2026-07-13, status 'open'), and open even for $n=2$. On the denominator: Schur [Sc16] showed $C^k\ll R_k(K_3)\ll k!$ for some $C>0$, and Erdős conjectured (cf. erdosproblems.com/183) that $R_k(K_3)\leq C^k$. On the numerator: Bondy–Erdős [BoEr73] and Erdős–Graham [ErGr75] proved $n2^k+1\leq R_k(C_{2n+1})\leq 2n(k+2)!$; the lower bound is sharp for fixed $k$ and large $n$ (Jenssen–Skokan [JeSk21]), and for fixed $n$ Day–Johnson [DaJo17] proved $R_k(C_{2n+1})\geq 2n(2+c_n)^{k-1}$ for large $k$ with some $c_n>0$. The best current upper bound is due to Axenovich, Cames van Batenburg, Janzer, Michel, and Rundström [ACJMR25]: $R_k(C_{2n+1})\leq(4n-2)^k k^{k/n}+1$, whence $R_k(C_{2n+1})\leq(Cn)^k(k!)^{1/n}$ for an absolute $C>0$. Because $R_k(K_3)$ is only pinned between $C^k$ and $k!$, the ratio question is delicate — it is the interplay of these bounds, not any single one, that must be controlled. Catalogued as #23 (multicolour Ramsey numbers of odd cycles) in the UCSD graphs problem collection. Attacker's tool: this is proof-shaped — a solver brings sharper analytic upper bounds on $R_k(C_{2n+1})$ (in the style of [ACJMR25]) together with lower bounds on $R_k(K_3)$, or a Lean formalization of the asymptotic reduction; direct computation of these $k$-colour Ramsey numbers is infeasible beyond $k=3$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #554 (T. F. Bloom) | website |
| REF-02 | Multicolour Ramsey numbers of odd cycles (#23, UCSD graphs problem collection) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.