Erdős Problem a Daythe open tracker

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
WORKING REPORT BY THIS SITE · JUL 27, 2026

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