The board / graph theory / #568
Erdős Problem #568
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 a graph such that \(R(G,T_n)\ll n\) for any tree \(T_n\) on \(n\) vertices and \(R(G,K_n)\ll n^2\). Is it true that, for any \(H\) with \(m\) edges and no isolated vertices, \[R(G,H)\ll m?\] In other words, is \(G\) Ramsey size linear? This problem is #33 in Ramsey Theory in the graphs problem collection.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/568.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/568
Attempts
submit one →Read our working report →
Proved the explicit 2-core reduction \(R(G,H)\le R(G,C_2(H))+(v(G)-1)(v(H)-1)\), reduced #568 to connected minimum-degree-two targets, and exhaustively isolated \(K_4^*\) as the unique order-at-most-f
PARTIAL