---

Claim. Assuming the continuum hypothesis, there is a graph $G$ whose vertex set is ordered in type $\omega_1^2$ such that $G$ contains no triangle and no complete bipartite graph $K_{\aleph_0,\aleph_0}$, and no set of vertices of order type $\omega_1^2$ is independent in $G$ (the abstract, in the corpus's words). Coloring a pair of vertices red when it is an edge of $G$ and blue otherwise gives a $2$-coloring of $[\omega_1^2]^2$ with no red triangle and no blue set of type $\omega_1^2$, that is,

$$\omega_1^2\not\to(\omega_1^2,3)^2 .$$

So the relation of Problem 1169 holds in every model of CH, and ZFC does not refute it, which is what the site's label, not disprovable, records. Whether ZFC proves it, equivalently whether $\omega_1^2\to(\omega_1^2,3)^2$ is consistent, is open: Komjáth's survey (Problem 13 commentary, on the corpus's source card) says the consistency is open as far as its author knows, and records, under the GCH heading of the survey's Problem 13, that the theorem is the case $\kappa=\omega$ of Hajnal's $(\kappa^+)^2\not\to((\kappa^+)^2,3)^2$ for $\kappa^{<\kappa}=\kappa$, that is, for regular $\kappa$ under GCH, so with the cardinal-arithmetic hypothesis $\kappa^{<\kappa}=\kappa$ together with $2^\kappa=\kappa^+$; at $\kappa=\omega$ the first condition holds in ZFC and the second is CH, which Hajnal's abstract assumes. Komjáth adds Baumgartner's extensions to singular $\lambda$ with $2^\lambda=\lambda^+$ and to regular $\kappa$ carrying a $\kappa$-Suslin tree, the latter recorded on Baumgartner's page. The graph's omission of $K_{\aleph_0,\aleph_0}$ is more than the relation needs.

Covers. One side of an independence result: the relation holds in every model of CH, so ZFC does not refute it, but nothing here shows that ZFC does not prove it. One side alone leaves the question open, so the result leaves Problem 1169 open. It would be settled as independent by a model of $\omega_1^2\to(\omega_1^2,3)^2$, which no source records, and as proved by a proof of the negative relation in ZFC alone.

Formulation. The catalog's statement quantifies over finite $k<\omega$, but the displayed relation does not use $k$; the booklet item [Va99, 7.85] asks the same question without the quantifier. Read with $k$ triangle colors, the relation at $k=0$ is $\omega_1^2\not\to(\omega_1^2)^2_1$, which is false, since with one color every set is homogeneous; so the statement quantified over all finite $k$ is false outright under that reading, which supports taking the displayed relation without $k$ as the target. The standing recorded here concerns the two-color relation as displayed.

Source. A. Hajnal, A negative partition relation, Proc. Nat. Acad. Sci. U.S.A. 68 (1971), no. 1, 142--144, doi:10.1073/pnas.68.1.142. The issue is dated January 1971 and the record carries no day, so this page's date is the first of that month. The statement above follows the paper's abstract. Nothing on this page is independently reviewed by this project.

Acceptance. Refereed: the result is a journal paper in the Proceedings of the National Academy of Sciences. Reviewed: the curator of erdosproblems.com, T. F. Bloom, labels Problem 1169 not disprovable and credits Hajnal [Ha71] with the proof under the continuum hypothesis (problem page last edited 25 January 2026); Komjáth's survey independently attributes the theorem to this paper. The curator and Komjáth are independent of the author.

Depends on. No other wiki page; the claim rests on the paper above.