Erdős #1169 — ω₁²↛(ω₁²,3)² is solved under CH (Hajnal 1971); ZFC status open

Statement

Is it true that $\omega_1^2 \not\to (\omega_1^2, 3)^2$? I.e.: does there exist a 2-colouring of the pairs from a set of order type $\omega_1^2$ (equivalently: a graph $G$ on a vertex set of order type $\omega_1^2$) such that $G$ contains no triangle, and $G$ has no independent set of order type $\omega_1^2$? (erdosproblems.com/1169, problem of Erdős and Hajnal, [Va99, 7.85].)

This is the $\omega_1$-level instance of the general "partition ordinal" question $\alpha\to(\alpha,3)^2$ studied throughout the Erdős–Hajnal ordinal-Ramsey program (see Ordinal partition calculus — arrow notation $\\alpha\\to(\\alpha,m)^2$ and the self-partitioning-ordinal program and its flagship countable-ordinal case Erdős #592 — characterize the countable partition ordinals).

Facts

- Status on erdosproblems.com (2026-07-02 fetch): OPEN in general — tagged "Not disprovable: open in general, but there exist models of set theory where the result is true." This is *not* a fully solved Erdős problem in the strict site-taxonomy sense. - What actually is solved, and is the load-bearing result this page documents: Hajnal proved $\omega_1^2\not\to(\omega_1^2,3)^2$ is TRUE assuming CH — A. Hajnal, "A negative partition relation," *Proc. Nat. Acad. Sci. U.S.A.* 68(1) (1971), 142–144 (MR 270952). Abstract (verified verbatim via PMC/PubMed): "If the continuum hypothesis is assumed, there is a graph $G$ whose vertices form an ordered set of type $\omega_1^2$; $G$ does not contain triangles or complete even graphs of form $K_{\aleph_0,\aleph_0}$, and there is no independent subset of vertices of type $\omega_1^2$." - The open part is exactly the ZFC-necessity question: is CH (or *some* extra axiom beyond ZFC) actually needed, or does $\omega_1^2\not\to(\omega_1^2,3)^2$ hold outright in ZFC? erdosproblems.com's "open in general" status reflects that no ZFC-only proof or independence result is known — 55 years after Hajnal's paper this remains unresolved. - The CH hypothesis has been progressively weakened (this is the documented literature arc, per arXiv:1801.00238 §1, §3-4, Fact 1.1): - Takahashi (1987), "Two negative partition relations," *Period. Math. Hungar.* 18(1):1–6 — isolates that Hajnal's argument only needs a specific diagonalization/"guessing" cardinal characteristic (the *stick number* at $\aleph_0$, following Brendle's "sticks and clubs" terminology) to equal $\aleph_1$, not full CH; proves $\omega_1^2\not\to(\omega_1^2,3)^2$ from ZFC + (stick number $=\aleph_1$), a strictly weaker hypothesis than CH, and notes the argument generalizes to arbitrary regular $\kappa$. - Larson (1998), "An ordinal partition from a scale" — generalizes to: $\kappa$ regular and $\mathfrak d_\kappa=\kappa^+$ (dominating number) implies $\kappa^{+\kappa}\not\to(\kappa^{+\kappa},3)^2$ and $(\kappa^+)^2\not\to((\kappa^+)^2,3)^2$; for $\kappa=\omega$, $\mathfrak d=\aleph_1$ is again strictly weaker than CH. - Lambie-Hanson & Weinert (2017) and Chen, Garti & Weinert (2018, arXiv:1801.00238) further calibrate exactly which combinations of cardinal characteristics ($\mathfrak b_\kappa$, stick number, etc. all $=\kappa^+$) suffice, framing the whole literature as "how much of CH is actually needed." - None of this closes the gap to ZFC; it only shows CH can be replaced by strictly weaker (but still non-ZFC-provable) hypotheses. - Related problem: Erdős #592 — characterize the countable partition ordinals — the flagship countable-ordinal analogue ($\omega^\beta\to(\omega^\beta,3)^2$, characterize which $\beta$; \$1000 prize), explicitly cross-referenced from erdosproblems.com/1169 as "a similar problem concerning countable ordinals." Also compare $\omega_1\not\to(\omega_1,\omega+2)^2$ (also from CH, Hajnal 1960, [960Ha]), the $\omega_1$-cardinal-level sibling negative relation in the same technique family. - Formalization: none found — the erdosproblems.com page itself confirms no Lean statement exists yet in google-deepmind/formal-conjectures.

Solution

The result that is actually proved (not the open ZFC question): under CH, $\omega_1^2\not\to(\omega_1^2,3)^2$.

The transferable technique — CH-powered diagonalization against all potential homogeneous sets, later refined to "isolate the minimal guessing principle."

1. The base move (Hajnal 1971). Under CH, $\omega_1$ can be enumerated as $2^{\aleph_0}$, i.e. every initial segment of the construction only ever has to "remember" countably much information, while there are only $\aleph_1$ many potential order-type-$\omega_1^2$ subsets to defeat. This is the standard shape of CH-based negative Ramsey/partition constructions at $\omega_1$ (the same shape underlies Sierpiński-style colorings and the classical Erdős–Rado-optimal "least point of disagreement" coloring $\Delta_\kappa(x,y)=\min\{i: x(i)\neq y(i)\}$ that witnesses $2^\kappa\not\to(3)^2_\kappa$ in general, cf. Lambie-Hanson & Soukup, arXiv:2002.02480, §1 — a structurally related but not identical family): build the coloring/graph by transfinite recursion of length $\omega_1$, using CH to enumerate in advance all $\aleph_1$-many candidate countable "pieces" that could later combine into a forbidden triangle or into an order-type-$\omega_1^2$ independent set, and at each stage make a local choice that kills the next candidate on the list while respecting all prior constraints. The order-type target $\omega_1^2$ (rather than just cardinality $\aleph_1$) makes this delicate — you must diagonalize against *order-type*, not just size, so the recursion has to track $\omega_1$-many "columns" (a coloring of $\omega_1\times\omega_1$, since $\omega_1^2$ as an ordinal is order-isomorphic to $\omega_1\times\omega_1$ lexicographically), and the CH enumeration lets a single pass of length $\omega_1$ visit every relevant countable substructure exactly once. 2. The generalizing move (Takahashi 1987, then Larson 1998, Lambie-Hanson–Weinert 2017, Chen–Garti–Weinert 2018). The full strength of CH is never actually used — only a "guessing"/diagonalization sub-principle is: a *stick*-type cardinal characteristic (a minimum-size family of $\aleph_0$-subsets of $\aleph_1$ that is cofinal under $\subseteq$ in $[\aleph_1]^{\aleph_1}$; Brendle's "sticks and clubs" framework, Fuchino–Shelah–Soukup 1997) equal to $\aleph_1$ is exactly the "can pre-enumerate enough guesses to diagonalize against every candidate homogeneous set" ingredient CH happened to supply. Once isolated, the same diagonalization scheme runs verbatim off this weaker hypothesis, and the technique transplants immediately to the dominating-number version ($\mathfrak d=\aleph_1$) and to a general regular $\kappa$. Chen–Garti–Weinert (arXiv:1801.00238, abstract, Fact 1.1, Theorem 3.1/4.1) present this explicitly as a research programme: "In early work in this area, many negative partition relations involving ordinals $\le\omega_1$ were shown to follow from the assumption of CH. Subsequently, this assumption was reduced in many cases to $\mathfrak{cc}=\aleph_1$ ... This gives a way of calibrating more precisely how much of CH is actually needed." 3. Why this is the reusable idea for downstream/open problems. The pattern — (a) find *a* CH-based diagonalization proof of a negative partition relation, then (b) strip the proof down to the single combinatorial "guessing" cardinal characteristic it actually consumes, then (c) ask whether *that* characteristic can itself be forced to $\aleph_1$ (or shown $>\aleph_1$) independently of CH — is the standard research move for the entire "is CH really necessary here?" question class in ordinal/cardinal partition calculus. It is exactly the open question left on #1169 itself (can the hypothesis be reduced all the way to nothing, i.e. is the relation a ZFC theorem, or is it independent of ZFC?), and it is the same move used on the sibling relation $\omega_1\not\to(\omega_1,\omega+2)^2$ (Hajnal 1960 under CH → Todorčević 1989 under $\mathfrak b=\aleph_1$ → Raghavan–Todorčević 2016 under "exists a Suslin tree" → Chen–Garti–Weinert under stick $=\aleph_1$), and on the more recent singular-cardinal analogue of the whole Erdős–Hajnal negative-relation programme (arXiv:2502.16625, 2025, on $\aleph_{\omega+1}\not\to(\aleph_{\omega+1},(3)_{\aleph_0})^2$ without GCH) — showing the "CH-necessity" question this page documents for #1169 is a live, actively-worked meta-question across the whole family, not a dead end specific to one problem.

Bottom line for downstream use: the "Hajnal negative-relation trick" = (i) enumerate $\aleph_1$-many potential bad substructures using CH (or a weaker guessing principle), (ii) transfinite-recurse a coloring of length $\omega_1$ that locally defeats the next enumerated candidate at each stage while preserving triangle-freeness, (iii) afterward, isolate the *minimal* cardinal characteristic the diagonalization actually needs and ask whether it can be decoupled from CH. This is the concept page to link as `concept/ch-diagonalization-negative-partition`.

Related

- Erdős #592 — characterize the countable partition ordinals — the flagship open countable-ordinal analogue (characterize $\beta$ with $\omega^\beta\to(\omega^\beta,3)^2$, \$1000 prize); erdosproblems.com/1169 explicitly cross-references it as "a similar problem concerning countable ordinals." - Ordinal partition calculus — arrow notation $\\alpha\\to(\\alpha,m)^2$ and the self-partitioning-ordinal program — general framework for $\alpha\to(\beta,m)^2$-style ordinal Ramsey questions; already lists #1169 as "the analogous partition-ordinal question one cardinal up, at $\omega_1^2$; open in general, true under CH," confirming this page. - concept/ch-diagonalization-negative-partition — the transferable technique: CH-powered (or weak-guessing-principle-powered) transfinite diagonalization to build a triangle-free graph on $\omega_1^2$ with no large independent set; used by Hajnal 1971, Takahashi 1987, Todorčević 1989, Larson 1998, Chen–Garti–Weinert 2018. - concept/cardinal-characteristics-continuum — the stick number, dominating number $\mathfrak d$, unbounding number $\mathfrak b$, and splitting number $\mathfrak s$, whose "$=\aleph_1$" instances are what successively replaced full CH in this literature (Chen, Garti & Weinert, arXiv:1801.00238). - concept/delta-least-disagreement-coloring — the classical $\Delta_\kappa(x,y)=\min\{i:x(i)\neq y(i)\}$ triangle-free/odd-cycle-free coloring witnessing $2^\kappa\not\to(3)^2_\kappa$ in ZFC (Erdős–Rado optimality); the structurally closest ZFC-provable relative of the CH-conditional #1169 result (Lambie-Hanson & Soukup, arXiv:2002.02480).