The board / set theory / #1171
Erdős Problem #1171
NOT DISPROVABLEdatabase updated 2026-09-05
Open in general, but there are models of set theory in which it is true — so it can't be disproved from the usual axioms (ZFC) alone.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
**Erdős Problem 1171.** Is it true that for all finite \(k < \omega\), \[\omega_1^2 \to (\omega_1 \cdot \omega, \underbrace{3, \ldots, 3}_{k})^2_{k+1}?\] In any \((k+1)\)-coloring of the pairs of the complete graph on \(\omega_1^2\), either there is a color-0 set of order type \(\omega_1 \cdot \omega\), or there is a monochromatic triangle \(K_3\) in some non-zero color. The case \(k = 1\) (`erdos_1171.variants.k_one`) is the Erdős–Hajnal theorem [EH74].
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/1171.Prizenone
Topicsset theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/1171
Attempts
submit one →Read our working report →
The live problem remains open, but k=2 is a verified 1987 ZFC theorem; only k>=3 remains, with an exact triangle-free-cover/block-fusion reduction and a checked sharp C5 block obstruction.
PARTIAL