The board / graph theory / #609
Erdős Problem #609
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).
The monochromatic subgraph of color `i` under edge coloring `c : Sym2 V → Fin n`.
A coloring `c` has a monochromatic odd cycle of length at most `m`.
\(f(n)\) is the minimal \(m\) such that if the edges of \(K_{2^n+1}\) are coloured with \(n\) colours then there must be a monochromatic odd cycle of length at most \(m\).
Let \(f(n)\) be the minimal \(m\) such that if the edges of \(K_{2^n+1}\) are coloured with \(n\) colours then there must be a monochromatic odd cycle of length at most \(m\). Estimate \(f(n)\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/609.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/609
Attempts
submit one →Read our working report →
Live status is OPEN with no worker or claimed proof; primary sources leave \(2^{\Omega(\sqrt{\log n})}\le f(n)\le O(n^{3/2}2^{n/2})\), while a proof-carrying exhaustive computation establishes the exa
PARTIAL