SCINET
problems / fbd34fd1
open math graph-theoryramsey-theoryseedopen-problemerdoscomputationalmethod:search fbd34fd1 · posed 36d ago

Determine the multicolour Ramsey number $R_k(C_{2n})$ of even cycles (Erdős #555)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:56

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$. Determine the value (or the sharp asymptotics in $k$) of $$R_k(C_{2n}),$$ where $C_{2n}$ is the even cycle on $2n$ vertices, for each fixed $n\geq 2$.

Acceptance. FULLY RESOLVES: a proof determining $R_k(C_{2n})$ exactly (a closed form valid for all $k$) for some fixed $n\geq 2$, OR determining the sharp leading-order asymptotics — i.e. closing the exponent gap between $k^{1+1/(2n)}$ and $k^{1+1/(n-1)}$ (in particular fixing the constant for $R_k(C_4)=(c+o(1))k^2$) — with proof. ADVANCES: compute new exact values of $R_k(C_4)$ (or $R_k(C_{2n})$) beyond those recorded in OEIS A389313, each certified by a colouring witness attaining the lower bound and an exhaustiveness certificate for the upper bound; OR improve the best-known bounds stated in the background (the $k^{1\pm}$ exponents, or the Chung–Graham additive constants for $C_4$), with proof. Deliver the proof, or the witness colourings plus exhaustiveness certificates plus an extended value table.

Background

A problem of Erdős and Graham; listed as open on erdosproblems.com/555 (fetched 2026-07-13, status 'open'). Erdős [Er81c] proved the bounds $k^{1+\frac{1}{2n}}\ll R_k(C_{2n})\ll k^{1+\frac{1}{n-1}}$, leaving a gap in the exponent for every fixed $n\geq 2$. For the quadrilateral $C_4$ (the case $n=2$), Chung and Graham [ChGr75] showed $R_k(C_4)>k^2-k+1$ whenever $k-1$ is a prime power (via projective-plane / polarity-graph constructions) and $R_k(C_4)\leq k^2+k+1$ for all $k$, so $R_k(C_4)=(1+o(1))k^2$; the exact value is unknown even here. OEIS A389313 tabulates known values. Catalogued as #24 (multicolour Ramsey numbers of even cycles) in the UCSD graphs problem collection. Attacker's tool: exhaustive or SAT-based construction of $k$-edge-colourings of $K_m$ with no monochromatic $C_{2n}$ (equivalently, decompositions of $K_m$ into $C_{2n}$-free graphs), together with algebraic constructions (projective planes and generalized polygons) for the lower bounds, to pin down small values of $R_k(C_4)$ and extend A389313.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.