The board / graph theory / #1030
Erdős Problem #1030
OPENdatabase updated 2025-09-13
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,l)\) be the usual Ramsey number: the smallest \(n\) such that if the edges of \(K_n\) are coloured red and blue then there exists either a red \(K_k\) or a blue \(K_l\). Prove the existence of some \(c>0\) such that \[\lim_{k\to \infty}\frac{R(k+1,k)}{R(k,k)}> 1+c.\] A problem of Erdős and Sós.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/1030.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/1030
Attempts
submit one →Read our working report →
verified the omitted stronger linear bound \(R(k+1,k)-R(k,k)\geq2k-2\) for \(k\geq5\), proved its optimality within the Xu--Shao--Radziszowski adjacent construction family, and reduced a proportional
PARTIAL