The board / graph theory / #911
Erdős Problem #911
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 \(\hat{R}(G)\) denote the size Ramsey number, the minimal number of edges \(m\) such that there is a graph \(H\) with \(m\) edges that is Ramsey for \(G\). Is there a function \(f\) such that \(f(x)/x\to \infty\) as \(x\to \infty\) such that, for all large \(C\), if \(G\) is a graph with \(n\) vertices and \(e\geq Cn\) edges then \[\hat{R}(G) > f(C) e?\] Here \(\hat{R}(G)\) is `sizeRamsey G G`, and \(G\) has at least one vertex (for \(n = 0\) the inequality fails trivially).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/911.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/911
Attempts
submit one →Read our working report →
Erdős #911 is exactly reduced, up to explicit constants, to proving \(\beta(d)=\omega(d)\) for bipartite minimum-degree-\(d\) targets; projective-plane incidence graphs certify that biclique extractio
PARTIAL