---

Statement

Problem 3 (printed pp. 223--224) has two parts.

The triple relation (p. 223). The print calls $\mathfrak c\to(\omega+n,4)^3_2$ "an old result of Rado and myself" and suggests that $\omega+n$ "can perhaps be replaced by any $\alpha<\omega_1$ and 4 by any $n<\omega$, but I know nothing about this." The print writes the left side as a plain c and does not define it here.

Pairs from $\omega_1^2$ (pp. 223--224). The paper reports these results without proof:

• Erdős and Hajnal proved $\omega_1^2\to(\omega_1\omega,3)^2$, and could never show $\omega_1^2\to(\omega_1\omega,4)^2_2$.
• During the meeting, Baumgartner and Hajnal proved, assuming the continuum hypothesis, $\omega_1^2\not\to(\omega_1\omega,4)^2$; they also proved a three-color relation, printed $\omega_1^2\to(\omega_1\omega,3,3)^2_1$.
• Erdős and Hajnal could never decide $\omega_2\omega\to(\omega_2\omega,3)^2_2$, and Erdős reports having heard in October 1985 that Shelah had just proved it.

He then asks: "Perhaps if $G$ is any graph of power $\aleph_1$ which contains no $K_4$ then $\omega_1^2\to(\omega_1\omega,G)^2$. This is open even if $G$ is assumed to be finite." In a parenthesis he reports that Baumgartner had just shown $\omega_1^2\not\to(\omega_1\omega,K(\aleph_0,\aleph_0))^2$, and suggests instead that the positive relation perhaps holds if $G$ contains no $K(4)$ and no $K(\aleph_0,\aleph_0)$, adding that it may be necessary to restrict $G$ to finite order.

Source. P. Erdős, Some problems on finite and infinite graphs, Logic and Combinatorics (Arcata, Calif., 1985), Contemp. Math. 65, Amer. Math. Soc. (1987), 223--228; Problem 3, pp. 223--224, PDF pp. 1--2 of the Rényi archive's scan (printed p. $n$ = PDF p. $n-222$), read on the rendered page images. The edition read is identified in the source digest.

Read depth. Claims checked: the item was read clause by clause on the page images. The results it reports are given without proof, and none of them was checked here.

Proof pointer

None in the source. The Erdős--Rado relation is Theorem 31 of their 1956 partition calculus paper, as recorded on Problem 70.

Dependencies

None.

Bears on

• Problem 70: the suggestion that $\omega+n$ may be replaced by any countable ordinal and 4 by any finite number is this problem's question, cited there as [Er87]. The paper records no result on it beyond the Erdős--Rado relation.
• Problem 597: the closing parenthesis poses this problem's question, $G$ of power $\aleph_1$ with no $K_4$ and no $K(\aleph_0,\aleph_0)$, and its finite case; the sentence before it poses the weaker form excluding only $K_4$, which Baumgartner's reported relation answers in the negative, as the problem page explains. The paper records no result on the problem's own question.