The board / graph theory / #163
Erdős Problem #163
Burr-Erdős conjecture
PROVEDdatabase updated 2025-09-13
The statement as posed is true, and a proof exists.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
The Burr-Erdős conjecture: For any \(d\geq 1\) if \(H\) is a graph such that every subgraph contains a vertex of degree at most \(d\) then \[R(H)\ll_d n.\] Solved by Lee [Le17], who proved that \(R(H) \leq 2^{2^{O(d)}}n\). This problem is #9 in Ramsey Theory in the graphs problem collection. The linked formal proof (Codex and GPT-5.6 Sol) gives, for graphs `H` on `Fin n`, a natural constant `C ≥ 1` with `RamseyFor H (C * n)` (every red/blue colouring of `K_{C n}` contains a monochromatic copy of `H`); transporting along `Fintype.equivFin` gives the statement below.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved. The authoritative wording is on erdosproblems.com/163.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/163
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.