The board / set theory / #1175
Erdős Problem #1175
OPENdatabase updated 2026-01-23
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 \(\kappa\) be an uncountable cardinal. Must there exist a cardinal \(\lambda\) such that every graph with chromatic number \(\lambda\) contains a triangle-free subgraph with chromatic number \(\kappa\)? Shelah proved that a negative answer is consistent when \(\kappa = \lambda = \aleph_1\) (see `erdos_1175.variants.aleph_one`).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 2 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/1175.Prizenone
Topicsset theory, chromatic number
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/1175
Attempts
submit one →Read our working report →
Proved the finite-clique hierarchy \(\chi(G)\le\beth_{q-3}(\kappa)\), obtained uniform \(>\kappa\) consequences at \(\beth_\omega(\kappa)\) and its successor-cover extension, reduced exact \(\kappa\)
PARTIAL