The board / graph theory / #566
Erdős Problem #566
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 \(G\) be such that any subgraph on \(k\) vertices has at most \(2k-3\) edges. Is it true that, if \(H\) has \(m\) edges and no isolated vertices, then \(R(G,H) \ll m\)? In other words: if \(G\) is sparse (every induced subgraph on \(k\) vertices has \(≤ 2k-3\) edges), is \(G\) Ramsey size linear?
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/566.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/566
Attempts
submit one →Read our working report →
Proved \(R(K_4^*,nK_2)=2n+2\) for every \(n\ge2\) and computationally determined \(R(K_4^*,H)\) for every no-isolate \(H\) with at most four edges; the uniform \((2,3)\)-sparse problem remains open.
PARTIAL