The board / graph theory / #836
Erdős Problem #836
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 \(r\geq 2\) and let \(G\) be an intersecting \(r\)-uniform hypergraph with chromatic number \(3\). Must \(G\) contain \(O(r^2)\) many vertices? Vertices are counted in the union of the edges, so isolated vertices are excluded. Alon has provided a counterexample to the first question: this hypergraph is intersecting, its chromatic number is \(3\), and it has \(\asymp 4^r/\sqrt{r}\) many vertices.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/836.Prizenone
Topicsgraph theory, hypergraphs, chromatic number
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/836
Attempts
submit one →Read our working report →
Live page status is OPEN with 0 formal proof claims and no current worker, but its discussion page (accessed 2026-07-27) says “GPT-5.5 Pro claims a solution to the 2nd question here,” so the mandatory
SKIPPED