The board / graph theory / #554
Erdős Problem #554
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Let \(R_k(G)\) denote the minimal \(m\) such that if the edges of \(K_m\) are \(k\)-coloured then there is a monochromatic copy of \(G\). Show that \[\lim_{k\to \infty}\frac{R_k(C_{2n+1})}{R_k(K_3)}=0\] for any \(n\geq 2\). A problem of Erdős and Graham. The case \(n = 1\) is excluded since \(C_3 = K_3\). This problem is #23 in Ramsey Theory in the graphs problem collection.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 6 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/554.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/554
Attempts
submit one →Read our working report →
The live problem is open with no claimant or worker; current bounds miss by a \(k^{k/\ell}\) factor, and the report proves a precise colour-index-gap reduction plus fully checked finite certificates,
WALL