The board / graph theory / #832
Erdős Problem #832
DISPROVEDdatabase updated 2025-08-31
The statement as posed is false.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Let \(r\geq 3\) and \(k\) be sufficiently large in terms of \(r\). Is it true that every \(r\)-uniform hypergraph with chromatic number \(k\) has at least \[\binom{(r-1)(k-1)+1}{r}\] edges, with equality only for the complete graph on \((r-1)(k-1)+1\) vertices? This was disproved by Alon [Al85]. The validity of this conjecture for \(r=3\) remains open.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved. The authoritative wording is on erdosproblems.com/832.Prizenone
Topicsgraph theory, hypergraphs, chromatic number
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/832
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.