1 Ordinary partition relations for cardinals

If ${\lambda },{\kappa }_\nu $ ( $\nu <\gamma $ ) are cardinals, $1\leq r<{\omega }$ , then ${\lambda }\to ({\kappa }_\nu )^r_\gamma $ denotes the following statement: if $F:[{\lambda }]^r\to \gamma $ , then there are $\nu <\gamma $ , $A\in [{\lambda }]^{{\kappa }_\nu }$ such that F is homogeneously of color $\nu $ on $[A]^r$ . If this fails (i.e., there is F for which it is not true), we cross the arrow: ${\lambda }\not \to ({\kappa }_\nu )^r_\gamma $ . Erdős, Hajnal, and Rado worked toward a full discussion of this relation. Problems 1–5 cover some of the unsolved cases.

This is the negative stepping-up lemma, cf. [Reference Erdős, Hajnal, Máté and Rado45, Section 24]. The curious piece of notation, $1+{\kappa }_\nu $ , denotes that this is cardinal addition, i.e., $1+4=5$ and $1+\aleph _0=\aleph _0$ . The reference just mentioned reports on the following special cases already proved:

1. (a) All ${\kappa }_\nu $ are finite.

2. (b) ${\kappa }_0,{\kappa }_1$ are infinite, ${\kappa }_0$ regular.

3. (c) $r\geq 3$ , ${\kappa }_0$ is infinite, regular.

4. (d) $r\geq 3$ , ${\kappa }_0,{\kappa }_1$ are infinite.

5. (e) $r\geq 4$ , ${\kappa }_0$ is infinite.

This was proved by Shelah in [Reference Shelah152]. Essentially this was the last remaining case of the discussion of the relation ${\lambda }\to ({\kappa })^2_2$ .

Hajnal conjectured that under the same assumption the stronger ${\lambda }\to (\aleph _{\omega },4)^3$ holds. This conjecture has so far been unproven.

Problem 4 (Erdős, Hajnal, Rado).

Assume that ${\lambda }$ is singular, ${\lambda }$ and $\textrm {cf}({\lambda })$ are both $\aleph _0$ -inacessible. Does then

$$\begin{align*}{\lambda}\to({\lambda},\aleph_1)^2 \end{align*}$$

hold?

Here a cardinal ${\kappa }$ is $\aleph _0$ -inaccessible, if for $\mu <{\kappa }$ we have $\mu ^{\aleph _0}<{\kappa }$ . The conditions are necessary, as $\tau ^{\aleph _0}\not \to (\tau ^+,\aleph _1)^2$ and if $\textrm {cf}({\kappa })\not \to (\textrm {cf}({\kappa }),\aleph _1)^2$ , then ${\kappa }\not \to ({\kappa },\aleph _1)^2$ .

The simplest case is . In this case the second condition implies the first one by a remarkable theorem of Shelah: if , then , ([Reference Shelah158], see also in [Reference Abraham and Magidor2]). An Erdős–Rado theorem ([Reference Erdős, Hajnal, Máté and Rado45, Theorem 35.4]) states that the positive relation holds if is strong limit.

Shelah and Stanley in [Reference Shelah and Stanley170] constructed a historic forcing that preserves the value of $2^\tau $ up to some predetermined cardinal and adds a counterexample to . In [Reference Shelah and Stanley171] they deduced from the consistency of the existence of measurable cardinals the consistency of is not strong limit yet holds.

Problem 5 (Erdős, Hajnal, Rado).

Can one prove without assuming the GCH that

$$\begin{align*}\aleph_{{\omega}+1}\not\to(\aleph_{{\omega}+1},(3)_{\aleph_0})^2 \end{align*}$$

holds?

The proof that $2^{\lambda }={\lambda }^+$ implies ${\lambda }^+\not \to ({\lambda }^+,(3)_{\textrm {cf}({\lambda })})^2$ for ${\lambda }$ singular is in [Reference Erdős, Hajnal, Máté and Rado45, Section 20]. Notice that $2^{\textrm {cf}({\lambda })}\geq {\lambda }^+$ also implies the negative relation as $2^{\kappa }\not \to (3)^2_{\kappa }$ holds in general.

2 Ordinary partition relations for order types

Ordinary partition relations for countable ordinals are of the form ${\alpha }\to ({\beta },n)^2$ with ${\omega }<{\alpha },{\beta }<{\omega }_1$ , $n<{\omega }$ . The reason why only partitions of this form are considered is given by the following easy results: ${\theta }\not \to ({\omega }+1,4)^3$ for any countable order type ${\theta }$ and ${\alpha }\not \to ({\omega }+1,{\omega })^2$ ( ${\alpha }<{\omega }_1$ ).

It is equally easy to see, that if ${\alpha }\to ({\alpha },3)^2$ then ${\alpha }$ is AI (additively indecomposable, i.e., a power of ${\omega }$ ).

Specker proved in [Reference Specker173] that

$$ \begin{align*} \begin{aligned} {\omega}^2 &\to({\omega}^2,k)^2 \quad (k<{\omega}),\\ {\omega}^n &\not\to({\omega}^n,3)^2 \quad (3\leq n<{\omega}). \end{aligned} \end{align*} $$

E. C. Milner proved [Reference Milner127]

$$ \begin{align*} \begin{aligned} {\omega}^{{\alpha}3}&\not\to ({\omega}^{{\alpha}2+1},3)^2 \quad ({\alpha}<{\omega}_1) \\ {\omega}^4&\to ({\omega}^3,3)^2 \\ {\omega}^3&\to ({\omega}^2 l,k)^2 \quad (l,k<{\omega}). \end{aligned} \end{align*} $$

Erdős proved

$$\begin{align*}{\omega}^{{\alpha}2+1}\to({\omega}^{{\alpha}+1},4)^2 \quad ({\alpha}<{\omega}_1). \end{align*}$$

The usual technique of proving these theorems is based on a coding of an arbitrary coloring of $[{\omega }^n]^2$ into a coloring of ${}^m{\omega }$ , for some $m>n$ .

Independently Galvin, Hajnal, Haddad, and Sabbagh proved that if $F:[{}^k{\omega }]^2\to l$ , then there is an $A\in [{\omega }]^{\omega }$ such that $F|[{}^k A]^2$ is canonical, i.e., $F(\langle n_0,\dots ,n_{k-1}\rangle ,\langle m_0,\dots ,m_{k-1}\rangle )$ only depends on the truth values of $n_i=m_j$ , $n_i<m_j$ ( $i,j<k$ ) for $n_i,m_i\in A$ ( $i<k$ ) [Reference Haddad and Sabbagh72].

This suffices to show that for every $k<{\omega }$ there is $n<{\omega }$ such that ${\omega }^k\not \to ({\omega }^3,n)^2$ but is not strong enough to calculate the least such n.

This was the simplest unsolved case at the moment of writing [Reference Erdős and Hajnal41] but in reality the problem asked for a full characterization of ${\omega }^n\to ({\omega }^k,l)^2$ .

Haddad and Sabbagh [Reference Haddad and Sabbagh72], Hajnal, Galvin, E. C. Milner (unpublished)proved that

$$\begin{align*}{\omega}^4\to ({\omega}^3,4)^2 \end{align*}$$

but

$$\begin{align*}{\omega}^4\not\to ({\omega}^3,5)^2. \end{align*}$$

Eva Nosal in [Reference Nosal138] proved ${\omega }^n\to ({\omega }^3,2^{n-2})^2$ and

$$\begin{align*}{\omega}^n\not\to ({\omega}^3,2^{n-2}+1)^2 \quad (4\leq n<{\omega}). \end{align*}$$

Another result of Eva Nosal [Reference Nosal139] is ${\omega }^n\to ({\omega }^m,p)^2$ and ${\omega }^n\not \to ({\omega }^m,p+1)^2$ where

$$\begin{align*}p=2^{[\frac{n-1}{m-1}]}\end{align*}$$

$(5\leq m\leq n)$ .

For more colors, Darby and Larson proved in [Reference Darby and Larson20] that if $t=t_1+\ldots +t_m$ then

$$\begin{align*}{\omega}^{t+2}\not\to ({\omega}^3,2^{t_1}+1,\dots,2^{t_m}+1)^2 \end{align*}$$

and

$$\begin{align*}{\omega}^{t+3}\to ({\omega}^3,2^{t_1+1},\dots,2^{t_m+1})^2. \end{align*}$$

This was proved by C. C. Chang in [Reference Chang19]. The complicated (90 page long) original proof was somewhat simplified and generalized to ${\omega }^{\omega }\to ({\omega }^{\omega },k)^2$ ( $k<{\omega }$ ) by Milner (unpublished). Then Larson gave a reasonably short proof in [Reference Larson115], [Reference Larson116].

Galvin noticed that if ${\omega }^{\alpha }\to ({\omega }^{\alpha },3)^2$ and $2<{\alpha }<{\omega }_1$ then necessarily ${\alpha }$ is of the form ${\omega }^\xi $ . [Reference Galvin and Larson64]

For the formulation of the following results set $a(\gamma )=k$ where $\gamma =\gamma _1+\ldots +\gamma _k$ is the decomposition of $\gamma $ into nonzero AI ordinals with $\gamma _1\geq \ldots \geq \gamma _k$ .

Erdős and Hajnal raised the possibility that if ${\alpha }<{\omega }_1$ , $3\leq m<n<{\omega }$ then ${\alpha }\to ({\alpha },m)^2$ implies ${\alpha }\to ({\alpha },n)^2$ (as in the case of ${\alpha }={\omega }^2$ or ${\omega }^{\omega }$ ). This is false by Theorems 2 and 3, but Theorem 5 and the Conjecture imply that it holds for m sufficiently large.

Already in [Reference Erdős and Rado52] Erdős and Rado showed ${\omega }_1\to ({\omega }_1,{\omega }+1)^2$ . After that, this is a natural question.

Hajnal showed in [Reference Hajnal73] that under CH ${\omega }_1\not \to ({\omega }_1,{\omega }+2)^2$ holds. This is not as easy as it seems. Todorcevic in [Reference Todorcevic188] proved that if ${\mathfrak {b}}={\omega }_1$ , then ${\omega }_1\not \to ({\omega }_1,{\omega }:2)^2$ .

Raghavan and Todorcevic proved in [Reference Raghavan and Todorcevic145] that ${\omega }_1\not \to ({\omega }_1,{\omega }+2)^2$ also follows from the existence of an ${\omega }_1$ -Suslin tree.

Todorcevic proved in [Reference Todorcevic182] that it is consistent (in fact, follows from PFA) that ${\omega }_1\to ({\omega }_1,{\alpha })^2$ holds for every ${\alpha }<{\omega }_1$ . Erdős and Hajnal asked in [Reference Erdős and Hajnal42] if ${\omega }_1\to ({\omega }_1,{\alpha })^2$ follows from $\mathrm {MA}_{{\omega }_1}$ for ${\alpha }<{\omega }_1$ . In unpublished work, Todorcevic showed this for ${\alpha }={\omega }^2$ , but the general case is open.

Erdős and Rado showed in [Reference Erdős and Rado52] that if ${\kappa }>{\omega }$ is regular, then ${\kappa }\to ({\kappa },{\omega }+1)^2$ . For singular cardinals, the corresponding statement is unsolved: if ${\lambda }>\textrm {cf}({\lambda })>{\omega }$ , then ${\lambda }\to ({\lambda },{\omega }+1)^2$ . Standard theory gives this if ${\lambda }$ is strong limit. Shelah proved the statement if $2^{\textrm {cf}({\lambda })}<{\lambda }$ [Reference Shelah168].

Hajnal in [Reference Hajnal73] proved that CH implies ${\omega }_1\not \to ({\omega }_1,({\omega }:2))^2$ .

Laver proved that if and $\mathrm {MA}_{{\omega }_1}$ holds, then ${\omega }_2\not \to ({\omega }_2,({\omega }:2))^2$ . Interestingly, this cannot be lifted to ${\omega }_3$ : Todorcevic in [Reference Todorcevic181] proved that it is consistent that , $\mathrm {MA}_{{\omega }_2}$ holds, yet ${\omega }_3\to ({\omega }_3,({\omega }:2))^2$ .

Baumgartner proved with his thinning-out process that if GCH holds and ${\kappa }$ is regular, then in a cardinal and cofinality forcing extension and ${\kappa }^+\not \to ({\kappa }^+,({\omega }:2))^2$ [Reference Baumgartner7].

Extending Baumgartner’s thinnig-out forcing, Laver proved in [Reference Laver119] that if GCH holds and ${\kappa }$ is strongly Mahlo, then with some cardinal and cofinality preserving forcing a model is obtained where , weakly Mahlo, and ${\kappa }\not \to ({\kappa },({\omega }:2))^2$ .

Kunen proved in [Reference Kunen111] that if ${\kappa }$ is real valued measurable then ${\kappa }\to ({\kappa },{\alpha })^2$ for ${\alpha }<{\omega }_1$ (see also [Reference Fremlin62]).

Problem 9 was asked in this form, because ${\omega }_{{\omega }+1}\to ({\omega }_{{\omega }+1},{\omega }+1)^2$ by the Erdős–Rado theorem and ${\omega }_{{\omega }+1}\not \to ({\omega }_{{\omega }+1},{\omega }_1)^2$ by Sierpinski’s example giving ${\kappa }^\mu \not \to ({\kappa }^+,\mu ^+)^2$ where $\mu =\textrm {cf}({\kappa })$ . Raghavan and Todorcevic proved in [Reference Raghavan and Todorcevic145] that if ${\lambda }$ is an infinite cardinal and there is a ${\lambda }^+$ -Suslin tree and ${\lambda }^\mu>{\lambda }$ , then ${\lambda }^+\not \to ({\lambda }^+,\mu +2)^2$ holds. In particular, if there is an ${\omega }_{{\omega }+1}$ -Suslin tree, then ${\omega }_{{\omega }+1}\not \to ({\omega }_{{\omega }+1},{\omega }+2)^2$ .

Problem 10/A. Does

$$\begin{align*}{\omega}_1\to({\omega}2,{\omega}^2)^2 \end{align*}$$

or

$$\begin{align*}{\omega}_1\to({\omega}3)^2_2 \end{align*}$$

or

$$\begin{align*}{\omega}_1\to({\omega}+n)^2_3 \quad (n<{\omega}) \end{align*}$$

hold?

Various special cases of the general statement ${\omega }_1\to ({\alpha })^2_k$ ( ${\alpha }<{\omega }_1$ , $k<{\omega }$ ) were proved in [Reference Erdős and Rado52], [Reference Hajnal73], clearly Erdős and his friends were fascinated by the question. In [Reference Prikry143], Prikry proved ${\omega }_1\to ({\omega }:{\omega }_1,{\alpha })^2$ for ${\alpha }<{\omega }_1$ .

The general case was eventually proved by Baumgartner and Hajnal in [Reference Baumgartner and Hajnal10]. See the comments at Problem 11 on this proof using forcing and absoluteness. The results of Prikry and Baumgartner–Hajnal were extended by Todorcevic who in [Reference Todorcevic191] proved that for ${\alpha }<{\omega }_1$ and $k<{\omega }$ one has ${\omega }_1\to (({\alpha },{\omega }_1),({\alpha })_k)^2$ , i.e., if $f:[{\omega }_1]^2\to k$ , then either there are $H_0<H_1\subseteq {\omega }_1$ with $\textrm {tp}(H_0)={\alpha }$ , $\textrm {tp}(H_1)={\omega }_1$ such that is homogeneous in color 0, or else there is $K\subseteq {\omega }_1$ , $\textrm {tp}(K)={\alpha }$ , that K is homogeneous in color j for some $j>0$ .

In all his life, Hajnal was very proud of this argument.

Soon after the Baumgartner–Hajnal proof, Galvin gave a purely combinatorial proof of the theorem [Reference Galvin63].

The following conjecture, which implies the Baumgartner–Hajnal theorem, is open: ${\omega }_1\to ({\alpha },n)^3$ for ${\alpha }<{\omega }_1$ , $n<{\omega }$ . Erdős and Rado proved that if ${\theta }$ is a real order, then ${\theta }\to ({\omega }+n,4)^3$ ( $n<{\omega }$ ) ([Reference Erdős and Rado52], see a short proof by Jones, [Reference Jones89]). Milner and Prikry showed ${\omega }_1\to ({\omega }+n,4)^3$ [Reference Milner and Prikry128]), then ${\omega }_1\to ({\omega } 2+1,4)^3$ ([Reference Milner and Prikry129]. Recently Jones extended this to ${\omega }_1\to ({\omega } 2+1,n)^3$ ( $n<{\omega }$ ) [Reference A. L.92]. In unpublished work, Schipperus proved ${\omega }_1\to ({\omega }^2+1,4)^3$ .

In unpublished work, Hajnal showed that ${\omega }_2\not \to ({\omega }_1+2)^2_{{\omega }}$ and ${\omega }_2\not \to [{\omega }_1+{\omega }]^2_{{\omega }_1}$ are separately consistent with GCH. In [Reference Rebholz146], Rebholz deduced this from the existence of a gap-2 morass and $\diamondsuit $ .

In the positive direction, Erdős and Hajnal proved that if CH holds, then ${\omega }_2\to ({\omega }_1+n)^2_2$ holds for $n<{\omega }$ (unpublished).

Shelah proved that if GCH holds, ${\kappa }$ is regular, $|{\alpha }|^+<{\kappa }$ , then ${\kappa }^+\to ({\kappa }+{\alpha })^2_2$ [Reference Shelah151].

Baumgartner, Hajnal, and Todorcevic proved that if ${\kappa }>{\omega }$ is regular, $n<{\omega }$ , $2^{|{\alpha }|}<{\kappa }$ , then $(2^{<{\kappa }})^+\to ({\kappa }+{\alpha })^2_n$ [Reference Baumgartner, Hajnal and Todorčević12].

Shelah also proved that if ${\kappa }$ is strongly compact, ${\lambda }>{\kappa }$ is regular, ${\alpha }<{\kappa }$ is an ordinal, $\mu <{\kappa }$ is a cardinal, then $(2^{<{\lambda }})^+\to ({\lambda }+{\alpha })^2_\mu $ holds [Reference Shelah167].

Laver showed that if CH holds and there is a normal $(\aleph _2,\aleph _2,\aleph _0)$ -saturated ideal on ${\omega }_1$ , then ${\omega }_2\to ({\omega }_1 2+1,{\alpha })^2$ ( ${\alpha }<{\omega }_2$ ) [Reference Laver120]. Foreman and Hajnal proved that if the saturation property is replaced with the existence of an $\aleph _1$ -dense ideal, then this can be improved to ${\omega }_2\to ({\omega }^2_1+1,{\alpha })^2$ ( ${\alpha }<{\omega }_2$ ) [Reference Foreman and Hajnal56].

Kanamori [Reference Kanamori95] proved that if ${\kappa }$ is measurable, then ${\kappa }^+\to ({\kappa } 2+1,{\alpha })^2$ ( ${\alpha }<{\kappa }^+$ ).

Foreman and Hajnal in [Reference Foreman and Hajnal56] prove that if ${\kappa }$ is measurable, then ${\kappa }^+\to ({\alpha })^2_{\kappa }$ holds for ${\alpha }<\Omega ({\kappa })$ , where $\Omega ({\kappa })$ is a technically defined, very large ordinal, but $\Omega ({\kappa })<{\kappa }^+$ .

Erdős and Hajnal in [Reference Erdős and Hajnal42] raised the following weakening of Problem 10: if GCH holds then for every ${\alpha }<{\omega }_2$ there is ${\beta }<{\omega }_3$ with ${\beta }\to ({\alpha })^2_2$ . The following result of Shelah may be relevant here: it is consistent that CH holds, $2^{\aleph _1}$ is anything it can be, and $2^{\aleph _1}\not \to ({\omega }_1{\omega })^2_2$ [Reference Shelah164].

We notice that Problem 10 is false if the number of colors is infinite: if ${\kappa }$ is an infinite cardinal, then ${\kappa }^+\not \to ({\kappa }^{\omega }+1)^2_{\omega }$ holds by the Milner–Rado paradox (see [Reference Milner and Rado130]).

Here ${\lambda }$ is the order type of $(\mathbb {R},<)$ . These were the then simplest unknown cases of the conjecture ${\lambda }\to ({\alpha })^2_k$ ( ${\alpha }<{\omega }_1$ , $k<{\omega }$ ). The problem was eventually settled by the following result.

The proof used a metamatematical argument. It was first shown that $\mathrm {MA}_{|\phi |}$ implies the result, then a rather complicated argument was given showing that if $\phi \to ({\omega })^1_{\omega }$ , then it remains true in any ccc forcing extension, finally an argument of Silver was used to show that if $(S,<)$ is an ordered set, F is a coloring of $[S]^2$ , and F has a homogeneous subset of type ${\alpha }$ in some forcing extension, for some countable ${\alpha }$ , then it has one in the ground model. As each model has a ccc forcing extension satisfying $\mathrm {MA}_{{\kappa }}$ , for any cardinal ${\kappa }$ , the theorem follows.

Notice that the condition on $\phi $ is necessary, as $\phi \not \to ({\omega })^1_{\omega }$ implies $\phi \not \to ({\omega },{\omega }+1)^2$ as can readily be seen.

Todorcevic showed in [Reference Todorcevic186] that if $\pi $ is a partial order type with $\pi \to ({\omega })^1_{\omega }$ then $\pi \to ({\alpha })^2_k$ holds for ${\alpha }<{\omega }_1$ , $k<{\omega }$ . Further, if ${\kappa }$ is regular, ${\lambda }^{<{\lambda }}<{\kappa }$ , $\pi $ is a partial order type, $\pi \to ({\kappa })^1_{2^{<{\kappa }}}$ , then $\pi \to ({\kappa }+{\alpha })^2_2$ ( ${\alpha }<{\lambda }$ ).

Here ${\lambda }=\textrm {tp}(\mathbb {R},<)$ , $\phi $ is a real type, if $|\phi |\geq \aleph _1$ and ${\omega }_1,{\omega }^*_1\not \leq \phi $ . The answer is No by Sierpiński’s coloring and the Baumgartner–Hajnal theorem described at Problem 11.

In [Reference Erdős and Hajnal42], Erdős and Hajnal extends the question to the following. Let $(R,<)$ be an ordered set of order type $\phi $ . What are the implications between the following statements?

1. (i) R is uncountable and contains a countable dense set.

2. (ii) ${\omega }_1,{\omega }^*_1\not \leq \phi $ , $|\phi |\geq \aleph _1$ .

3. (iii) $\phi \to (\eta )^1_{{\omega }}$ .

4. (iv) $\phi \to ({\omega })^1_{{\omega }}$ .

5. (v) There is $\psi \leq \phi $ , $|\psi |\geq \aleph _1$ , ${\omega }^*_1\not \leq \psi $ .

Galvin showed that if ${\omega }_1\not \leq \phi $ then (iv) implies (iii).

Baumgartner proved the following.

For (a), Hajnal proved $({\kappa }^+)^2\not \to (({\kappa }^+)^2,3)^2$ if ${\kappa }^{<{\kappa }}={\kappa }$ in [Reference Hajnal76], i.e., for ${\kappa }$ regular under GCH. Baumgartner extended this to singular cardinals, he proved that if ${\lambda }$ is singular, $2^{\lambda }={\lambda }^+$ , then $({\lambda }^+)^2\not \to (({\lambda }^+)^2,3)^2$ . For non-successor cardinals, he further proved that if ${\lambda }$ is strong limit singular then ${\lambda }^2\to ({\lambda }^2,3)^2$ holds iff $\textrm {cf}({\lambda })^2\to (\textrm {cf}({\lambda })^2,3)^2$ . Further, if ${\kappa }$ is regular and there is a ${\kappa }$ -Suslin tree, then ${\kappa }^2\not \to ({\kappa }^2,3)^2$ [Reference Baumgartner6].

The consistency of ${\omega }^2_1\to ({\omega }^2_1,3)^2$ is, as far as I know, open.

In [Reference Erdős and Hajnal40], Erdős and Hajnal proved ${\omega }^2_1\to ({\omega }_1{\alpha },3)^2$ for ${\alpha }<{\omega }_1$ . Baumgartner and Hajnal in [Reference Baumgartner and Hajnal11] showed that CH implies ${\omega }^2_1\not \to ({\omega }_1{\omega },4)^2$ , but ${\omega }_1^2\to ({\omega }_1{\omega },3,3)^2$ holds in ZFC. This implies, via forcing and compactness, that there is a finite $K_4$ -free graph all whose edge coloring with two colors has a homogeneous triangle, see Problem 54.

(b) was solved by Shelah and Stanley in [Reference Shelah and Stanley170]. They proved that ${\omega }_2{\omega }\not \to ({\omega }_2{\omega },3)^2$ is consistent with the negation of CH. A sophisticated argument gives that CH implies ${\omega }_2{\omega }\to ({\omega }_2{\omega },k)^2$ for $k<{\omega }$ . GCH is consistent with both ${\omega }_3{\omega }_1\not \to ({\omega }_3{\omega }_1,3)^2$ and with ${\omega }_3{\omega }_1\to ({\omega }_3{\omega }_1,k)^2$ ( $k<{\omega }$ ), the latter modulo the consistency of a weakly compact cardinal.

Miyamoto in [Reference Miyamoto132] gave a morass proof of ${\omega }_3{\omega }_1\not \to ({\omega }_3{\omega }_1,3)^2$ , thereby confirming that this holds under V=L. Stanley, Velleman, and Morgan improved this argument by showing that if $2^{\aleph _1}=\aleph _2$ and there is a simplified $({\omega }_2,1)$ -morass with linear limits, then ${\omega }_3{\omega }_1\not \to ({\omega }_3{\omega }_1,3)^2$ holds [Reference Stanley, Velleman and Morgan174]. This implies that if GCH and ${\omega }_3{\omega }_1\to ({\omega }_3{\omega }_1,3)^2$ hold then either $\aleph _2$ or $\aleph _3$ is inaccessible in L.

3 Square bracket partition relations

Erdős and Hajnal proved $a\not \to [r]^r_{2^r}$ for $a,r\geq \aleph _0$ cardinals. They specifically asked the following special case of Problem 14.

It was pointed out by Laver [Reference Laver120], that the negation of this holds in a model of Kunen [Reference Kunen112].

Erdős and Hajnal proved that CH implies $\aleph _1\not \to [\aleph _1]^2_{\aleph _1}$ . Here they ask how much of this remains true under ZFC alone. We know, by Sierpiński, that .

(a) Shelah in [Reference Shelah160] proved that if the existence of a measurable cardinal is consistent then so is . This was specific about $\aleph _1$ and . In [Reference Shelah166] he proved that if $\mu =\mu ^{<\mu }<{\theta }<{\kappa }$ , ${\kappa }$ is strongly Mahlo, then a cardinal preserving forcing makes $2^\mu ={\kappa }$ and ${\kappa }\to [{\theta }]^2_{\sigma ,2}$ for every $\sigma <\mu $ .

For higher superscripts, he proved in [Reference Shelah163] that if ${\lambda }$ is ${\omega }$ -Mahlo, then in a ccc extension for some $h(r)<{\omega }$ .

(b) Galvin and Shelah proved $2^{\aleph _0}\not \to [2^{\aleph _0}]^2_{\aleph _0}$ [Reference Galvin and Shelah66].

(c) First Blass obtained $\aleph _1\not \to [\aleph _1]^2_3$ in [Reference Blass18]. This was quickly followed by Galvin and Shelah’s $\aleph _1\not \to [\aleph _1]^2_4$ [Reference Galvin and Shelah66]. Finally, Todorcevic showed $\aleph _1\not \to [\aleph _1]^2_{\aleph _1}$ using a powerful new method, the Todorcevic walks [Reference Todorcevic187].

Consider the following statements.

1. (a) $\square ({\kappa })$ and $\diamondsuit _k$ hold for every strongly inaccessible, not weakly compact cardinal.

2. (b) There is a ${\kappa }$ -Suslin tree for every strongly inaccessible, not weakly compact cardinal ${\kappa }$ .

3. (c) ${\kappa }\not \to [{\kappa }]^2_{\kappa }$ for every strongly inaccessible, not weakly compact cardinal ${\kappa }$ .

4. (d) ${\kappa }\not \to [{\kappa }]^2_{\omega }$ for every strongly inaccessible, not weakly compact cardinal ${\kappa }$ .

Here $(a)\rightarrow (b)\rightarrow (c)\rightarrow (d)$ . Of course, (d) can be replaced with ${\kappa }\not \to [{\kappa }]^2_\gamma $ for any $3\leq \gamma <{\kappa }$ .

Jensen proved (a) and therefore (b) in L (more exactly if $\diamondsuit (E)$ and $\square (E)$ hold where $E\subseteq {\kappa }$ is stationary and if $C_{\alpha }$ is in the square sequence then ), from which R. A. Shore deduced (c) in L. [Reference Shore172].

Woodin first proved the independence of (a) by showing that if $2^{\kappa }>{\kappa }^+$ and Radin forcing is applied to a measure sequence of length ${\kappa }^+$ , then in the resulting model ${\kappa }$ is inacessible and $\diamondsuit _{\kappa }$ fails.

Omer Ben-Neria, Shimon Garti, and Yair Hayut in [Reference Ben-Neria, Garti and Hayut16] proved that if ${\kappa }$ is measurable with $o({\kappa })\geq {\kappa }^+$ , $2^{\kappa }=2^{{\kappa }^+}$ , then in a generic extension ${\kappa }$ is inacessible and $\Phi _{\kappa }$ fails.

Golshani [Reference Golshani68] started with a ${\kappa }$ which is $({\kappa }+3)$ -strong and gave a forcing extension in which ${\kappa }$ is the least inaccessible and $\Phi _{\kappa }$ , consequently $\diamondsuit _{\kappa }$ fails.

Todorcevic [Reference Todorcevic187] and independently, but slightly later Shelah [Reference Shelah160], generalizing Todorcevic’s argument for $\aleph _1\not \to [\aleph _1]^2_{\aleph _1}$ , proved that if ${\kappa }>\aleph _1$ is regular and there is a nonreflective stationary set in ${\kappa }$ , then ${\kappa }\not \to [{\kappa }]^2_{\kappa }$ .

Finally Rinot proved in [Reference Rinot147] that if ${\kappa }$ is regular and ${\kappa }\to [{\kappa }]^2_{\kappa }$ , then ${\kappa }$ is weakly compact in L.

As much as we know, (b), (c), and (d) can be true in ZFC.

Todorcevic showed in [Reference Todorcevic185] that if $\square _{\lambda }$ holds, ${\lambda }\not \to [{\kappa }_{\alpha }]^r_{{\alpha }<\gamma }$ , then ${\lambda }^+\not \to [1+{\kappa }_{\alpha }]^{r+1}_{{\alpha }<\gamma }$ , assuming that each ${\kappa }_{\alpha }$ is infinite, regular ( ${\alpha }>0$ ).

In [Reference Erdős, Hajnal and Rado48], Erdős, Hajnal, and Rado claimed that GCH implied $\aleph _2\not \to [\aleph _1]^3_3$ . Erdős and Hajnal reported in [Reference Erdős and Hajnal42] that if ${\kappa }$ is regular, $k\leq 4$ , ${\lambda }\not \to [{\kappa }]^2_k$ , then $2^{\lambda }\not \to [{\kappa }]^3_k$ . In particular, $2^{\aleph _1}\not \to [\aleph _1]^3_4$ .

Todorcevic in [Reference Todorcevic190] proved $\aleph _2\not \to [\aleph _1]^3_{\aleph _0}$ and $2^{\aleph _1}\not \to [\aleph _1]^3_{10}$ .

Shelah noticed that if $2^{\kappa }\to [{\kappa }^+]^2_3$ then $(2^{\kappa })^+\to [{\kappa }^+]^3_3$ . The consistency of the former statement is proved in [Reference Shelah166].

In unpublished work Galvin proved that if $\phi $ is an order type, ${\omega }_1\not \leq \phi $ , $\eta \not \leq \phi $ , then

$$\begin{align*}\phi\not\to[{\omega},{\omega}^2,{\omega}^2,{\omega}^3,{\omega}^3,{\omega}^4,{\omega}^4,\dots]^2. \end{align*}$$

In particular, ${\omega }^{\omega }\not \to [{\omega }^{\omega }]^2_{\aleph _0}$ .

Galvin also proved that $\eta \to [\eta ]^2_3$ . He also conjectured and Laver proved that

$$\begin{align*}\left[ \begin{array}{c} \eta\\ \eta\\ \eta\\ \vdots\\ \eta \end{array} \right] \longrightarrow \left[ \begin{array}{c} \eta \\ \eta \\ \eta \\ \vdots\\ \eta \end{array} \right]^{1,1,\dots,1}_{t_k}. \end{align*}$$

for some number $t_k$ (k is the number of rows) but obtained the minimal value of $t_k$ wrong. That was finally calculated by Denis Devlin in [Reference Devlin22] (see also [Reference Todorcevic193, pp. 143–Reference Nesteril and Rödl134]).

As it was quickly realized, $\aleph _2\to [\aleph _1]^{2}_{\aleph _1,\aleph _0}$ is equivalent to $\aleph _2\to [\aleph _1]^{<{\omega }}_{\aleph _1,\aleph _0}$ , which is Chang’s conjecture (CC). It is easy to see that the negation of CC is consistent: a Kurepa tree is a counterexample to it. The consistency of CC was proved by Jack Silver from the existence of an ${\omega }_1$ -Erdős cardinal. Todorcevic proved [Reference Todorcevic190] that $\aleph _2\to [\aleph _1]_{\aleph _1}^3$ is equivalent to CC.

Erdős and Hajnal notice that this is equivalent to the Kurepa hypothesis.

Baumgartner proved in [Reference Baumgartner5] that it is consistent from a strongly inacessible that Problem 19/A $\not \longrightarrow $ Problem 19/B. See also [Reference Miyamoto133].

That is, are there stationary subsets $\{S_{\alpha }:{\alpha }<{\kappa }\}$ of ${\omega }_1$ such that is countable ( ${\alpha }\neq {\beta }$ ) for ${\kappa }=\aleph _2$ or $2^{\aleph _1}$ ?

An ideal I on ${\omega }_1$ is ${\kappa }$ -saturated if there are no sets with $A_{\alpha }\notin I$ such that for ${\alpha }\neq {\beta }$ . If ${\kappa }=\aleph _2$ , then there are $\aleph _2$ stationary sets in ${\omega }_1$ with pairwise nonstationary intersection iff there are $\aleph _2$ stationary sets with pairwise countable intersection.

First Magidor observed that if Jensen’s $\diamondsuit $ principle holds, then there are $2^{\aleph _1}$ stationary sets in ${\omega }_1$ with pairwise countable intersection.

In [Reference Kunen112], Kunen proved that from a huge cardinal it is consistent that there is an ${\omega }_1$ -complete, $\aleph _2$ -saturated ideal on ${\omega }_1$ .

In [Reference Steel and >van Wesep175] J. R. Steel, R. A. van Wesep proved the consistency of ZFC plus the non-stationary ideal on ${\omega }_1$ is $\aleph _2$ -saturated from a model of $\mathrm {AD}_{\mathbb {R}}$ and ${\theta }$ is regular.

In [Reference Foreman, Magidor and Shelah58], Foreman, Magidor, and Shelah proved the consistency of Martin’s maximum (MM) from a supercompact cardinal, and showed that MM implies that the non-stationary ideal on ${\omega }_1$ is $\aleph _2$ -saturated.

Shelah proved from the consistency of a Woodin cardinal that the nonstationary ideal is $\aleph _2$ -saturated.

In the last two models, CH fails. This is no accident: Woodin proved that if the nonstationary ideal on ${\omega }_1$ is $\aleph _2$ -saturated and a measurable cardinal exists, then CH fails [Reference Hugh Woodin196].

Here . If ${\lambda }$ is a cardinal, let $\mathrm {KH}_{\lambda }$ denote the existence of a family , such that for every infinite $X\subseteq {\lambda }$ . An easy argument shows that under GCH, $\mathrm {KH}_{\aleph _{\omega }}$ is equivalent to the above statement. Erdős, Hajnal, and Milner proved in [Reference Erdős, Hajnal and Milner47] that if GCH holds and ${\omega }<\textrm {cf}({\lambda })<{\lambda }$ then $\mathrm {KH}_{\lambda }$ fails. In unpublished work, Prikry proved that in L, $\mathrm {KH}_{\lambda }$ holds for every ${\omega }=\textrm {cf}({\lambda })<{\lambda }$ [Reference Prikry142]. Todorcevic improved upon this by showing that if ${\omega }=\textrm {cf}({\lambda })<{\lambda }$ , then $\square _{\lambda }$ implies $\mathrm {KH}_{\lambda }$ [Reference Todorcevic184, Reference Todorcevic185]. Yodorcevic proved that the Chang conjecture $(\aleph _{{\omega }+1},\aleph _{\omega })\to (\aleph _1,\aleph _0)$ implies that $\mathrm {KH}_{\aleph _{\omega }}$ fails ([Reference Todorcevic192], see also [Reference Yodorcevic189], [Reference Todorcevic187], and [Reference Todorcevic184]).

Recently Golshani proved that if ${\kappa }$ is supercompact, then $\mathrm {KH}_{\lambda }$ fails for ${\lambda }\geq {\kappa }$ [Reference Golshani69].

The following problem concerns of the so called Milner–Rado paradox [Reference Milner and Rado130]. This surprising statement states that ${\alpha }\not \to ({\kappa }^{\omega })^1_{{\omega }}$ holds for every ${\alpha }<{\kappa }^+$ .

Problem 20. If ${\kappa }$ , ${\lambda }$ are infinite cardinals, ${\kappa }^+<{\lambda }$ , ${\alpha }<{\lambda }^+$ is an ordinal, then

$$\begin{align*}{\alpha}\not\to[{\lambda}^{{\kappa}^+}]^1_{{\kappa}^+,{\kappa}}. \end{align*}$$

The following is an important special case.

Erdős and Hajnal proved the following partial results:

1. (1) ${\alpha }\not \to [{\omega }^{{\omega }_1}_2]^1_{\aleph _1,\aleph _0}$ ( ${\alpha }<{\omega }^{{\omega }_2}_2$ ),

2. (2) if ${\omega }^{{\omega }_2}_2\not \to [{\omega }^{{\omega }_1}_2]^1_{}$ then the answer to Problem 19/D is affirmative.

Problem 21/A. Let ${\alpha }<{\omega }_3$ . Does there exist a sequence $\langle f_{\beta }:{\beta }<{\alpha }\rangle $ of ${\omega }_1\to {\omega }_1$ functions such that if ${\beta }_0<{\beta }_1<{\alpha }$ then

$$\begin{align*}|\{\xi<{\omega}_1:f_{{\beta}_0}(\xi)\geq f_{{\beta}_1}(\xi)\}|\leq\aleph_0? \end{align*}$$

In his thesis, Kunen proved that under GCH, the statement in Problem 21/A fails for large enough $a<{\omega }_3$ . On the other hand for any ${\alpha }<{\omega }_3$ , a forcing argument gives the consistent existence of such a sequence [Reference Kunen111].

If ${\kappa }>{\omega }$ is regular, an easy recursion gives the existence of a sequence $\{h_{\alpha }:{\alpha }<{\kappa }^+\}\subseteq {}^{\kappa }{\kappa }$ such that $h_{\beta }<^* h_{\alpha }$ , i.e., $\{\xi <{\kappa }:h_{{\beta }}(\xi )\geq h_{{\alpha }}(\xi )\}$ is bounded for ${\beta }<{\alpha }<{\kappa }^+$ , see [Reference Foreman55, pp. 906–907] and [Reference Komjáth and Totik109, Chapter 22].

Here $h_{\alpha }$ is the ${\alpha }$ th canonical function, i.e., if $S\subseteq {\kappa }$ is stationary, $f:S\to \textrm {ORD}$ has $f(\xi )<h_{\alpha }(\xi )$ for $\xi \in S$ , then there is stationary $S^*\subseteq S$ , such that $f|S^*=h_{\beta }|S^*$ for some ${\beta }<{\alpha }$ .

In 1976, Hajnal proved that in L there is no ${\omega }_2$ -th canonical function (unpublished, but see [Reference Jech87, pp. 554–555]). Jech and Shelah proved that if CH holds and ${\theta }$ is an ordinal, then in a cardinal and cofinality preserving extension for every ${\alpha }<{\theta }$ there is an ${\alpha }$ th function [Reference Jech and Shelah88].

Deiser and Donder proved that the statement that $c_{{\omega }_1}$ (the constant ${\omega }_1$ function on ${\omega }_1$ ) is the ${\omega }_2$ nd canonical function on ${\omega }_1$ is equiconsistent with the existence of an inaccessible limit of measurable cardinals [Reference Deiser and Donder21]. This was extended by Larson and Shelah, who proved that the above condition suffices to give a model where $c_{{\omega }_1}$ is the ${\omega }_2$ nd canonical function and CH holds [Reference Paul Larson117].

If ${\kappa }$ , $\mu $ are cardinals, then ${\kappa }\Longrightarrow (\mu )^{<{\omega }}$ abbreviates the following statement: if $F:[{\kappa }]^{<{\omega }}\to 2$ with no $[X]^r\subseteq F^{-1}(0)$ for $X\in [{\kappa }]^{r+1}$ ( $r<{\omega }$ ), then there exist $r_0<{\omega }$ and $Y\in [{\kappa }]^\mu $ such that $[Y]^r\subseteq F^{-1}(1)$ for $r_0<r<{\omega }$ .

This follows from the following theorem independently proved by J. E. Baumgartner and Erdős–Hajnal–Rado. If $a_r<b_r<{\omega }$ for $1\leq r<{\omega }$ , $a_r\to \infty $ , and $f_r:[{\omega }]^r\to b_r$ , then there are an infinite $A\subseteq {\omega }$ and $r_0<{\omega }$ such that $|F_r[[A]^r]|\leq a_r$ for $r>r_0$ . This is unpublished, but it was a problem in the 1968 M. Schweitzer Commemorative Contest, see [Reference Hajnal75], [176].

4 Polarized partition relations

Problem 24 (Erdős, Hajnal, Rado) (GCH).

Does

$$\begin{align*}\left( \begin{array}{c} \aleph_2 \\ \aleph_1 \end{array} \right) \rightarrow \left( \begin{array}{cc} \aleph_i & \aleph_j \\ \aleph_1 & \aleph_1 \end{array} \right)^{1,1} \end{align*}$$

hold for $0\leq i,j\leq 1$ ?

Prikry proved in [Reference Prikry141] the consistency of GCH with

$$\begin{align*}\left( \begin{array}{c} \aleph_2 \\ \aleph_1 \end{array} \right) \not\rightarrow \left( \begin{array}{c} \aleph_0 \\ \aleph_1 \end{array} \right)^{1,1}_{\aleph_0}. \end{align*}$$

His proof was the first example of forcing with side conditions. In [Reference Prikry141], he also gives the consistency of the following stronger assertion with GCH.

$(*)$ There are sets $A({\alpha },\xi )\subseteq {\omega }_1$ ( ${\alpha }<{\omega }_2$ , $\xi <{\omega }_1$ ) such that $\langle A({\alpha },\xi ):\xi <{\omega }_1\rangle $ is a partition of ${\omega }_1$ ( ${\alpha }<{\omega }_2$ ) and if $s\in [{\omega }_2]^{\aleph _0}$ , $f:s\to {\omega }$ , then

$$\begin{align*}\left| {\omega}_1- \bigcup\{A({\alpha},f({\alpha})):{\alpha}\in s\} \right|\leq\aleph_0. \end{align*}$$

This is easily seen to imply the square bracket polarized partition relation

$$\begin{align*}\left[ \begin{array}{c} \aleph_2 \\ \aleph_1 \end{array} \right] \not\rightarrow \left[ \begin{array}{c} \aleph_0 \\ \aleph_1 \end{array} \right]^{1,1}_{\aleph_1}. \end{align*}$$

In [Reference Prikry144] Prikry reports that in unpublshed work, Jensen deduced $(*)$ from $V=L$ .

For the other direction, Laver [Reference Laver120] proved from the consistency of the existence of a huge cardinal that GCH is consistent with the existence of an $(\aleph _2,\aleph _2,\aleph _0)$ saturated ideal on ${\omega }_1$ and the latter implies

$$\begin{align*}\left( \begin{array}{c} \aleph_2 \\ \aleph_1 \end{array} \right) \rightarrow \left( \begin{array}{c} \aleph_1 \\ \aleph_1 \end{array} \right)^{1,1}_{\aleph_0}. \end{align*}$$

In unpublished work, Galvin generalized this to

$$\begin{align*}\left( \begin{array}{c} \aleph_2 \\ \aleph_1 \end{array} \right) \rightarrow \left( \begin{array}{c} {\alpha} \\ \aleph_1 \end{array} \right)^{1,1}_{\aleph_0} \quad ({\alpha}<{\omega}_2) \end{align*}$$

(see the reference in [Reference Laver120] and see also [Reference Jones90]).

Problem 25 (Erdős, Hajnal, Rado) (GCH).

Does

$$\begin{align*}\left( \begin{array}{l} \aleph_{{\omega}+1} \\ \aleph_{{\omega}+1} \end{array} \right) \rightarrow \left( \begin{array}{ll} \aleph_{{\omega}+1} & \aleph_1 \\ \aleph_{\omega} & \aleph_{\omega} \end{array} \right)^{1,1} \end{align*}$$

hold?

Garti proves the consistency of

$$\begin{align*}\left( \begin{array}{l} {\lambda}^+ \\ {\lambda} \end{array} \right) \not\rightarrow \left( \begin{array}{ll} {\lambda}^+ & \aleph_1 \\ {\lambda} & {\lambda} \end{array} \right)^{1,1} \end{align*}$$

for some strong limit singular ${\lambda }$ with $\textrm {cf}({\lambda })={\omega }$ and notices that standard modification can give ${\lambda }=\aleph _{\omega }$ [Reference Garti67].

Problem 26. Does

hold without the assumption of CH?

To give a model of and the negative relation is fairly standard: one can add $\aleph _2$ Cohen reals or use a model of $\mathrm {MA}_{{\omega }_1}$ .

The positive statement follows from the existence of an $\aleph _1$ -generated selective ultrafilter on ${\omega }$ . Models for this (and not CH) were given by Kunen (unpublished) and later by Baumgartner and Laver [Reference Baumgartner13] (cf. Problem 40).

Problem 27 (GCH).

Does

$$\begin{align*}\left( \begin{array}{c} \aleph_2 \\ \aleph_1 \end{array} \right) \not\rightarrow \left( \begin{array}{c} \aleph_0 \\ \aleph_1 \end{array} \right)^{1,1}_{\omega} \end{align*}$$

hold?

In unpublished work, Hajnal proved that GCH implies

$$\begin{align*}\left( \begin{array}{l} \aleph_{2} \\ \aleph_{2} \end{array} \right) \rightarrow \left( \begin{array}{ll} \aleph_{1} \\ \aleph_1 \end{array} \right)^{1,1}_3 \end{align*}$$

and

$$\begin{align*}\left( \begin{array}{l} \aleph_{3} \\ \aleph_{2} \end{array} \right) \rightarrow \left(\left( \begin{array}{l} \aleph_{0} \\ \aleph_1 \end{array}\right)_{\aleph_0} \left(\begin{array}{l}\aleph_2\\ \aleph_2\end{array}\right) \right)^{1,1}. \end{align*}$$

See also the remarks on Prikry’s and Laver’s results at Problem 24.

In [Reference Erdős, Hajnal and Rado48] it is proved that GCH implies

$$\begin{align*}\left( \begin{array}{l} \aleph_{2} \\ \aleph_{2} \end{array} \right) \rightarrow \left( \begin{array}{l} \aleph_{2} \\ \aleph_1 \end{array} \lor \begin{array}{l} \aleph_{1} \\ \aleph_2 \end{array} , \begin{array}{l} \aleph_1\\ \aleph_1\end{array} \right)^{1,1}. \end{align*}$$

With Prikry’s method the consistency each of the following can be shown to be consistent with GCH:

$$\begin{align*}\left( \begin{array}{l} \aleph_{2} \\ \aleph_{2} \end{array} \right) \rightarrow \left( \begin{array}{ll} \aleph_{1} \\ \aleph_1 \end{array} \right)^{1,1}_4 \end{align*}$$

and

$$\begin{align*}\left( \begin{array}{l} \aleph_{2} \\ \aleph_{2} \end{array} \right) \not\rightarrow \left( \begin{array}{l} \aleph_{2} \\ \aleph_1 \end{array} \lor \begin{array}{l} \aleph_{1} \\ \aleph_2 \end{array} , \left( \begin{array}{l} \aleph_1\\ \aleph_1\end{array} \right)_2 \right)^{1,1}. \end{align*}$$

Problem 28.

$$\begin{align*}\left( \begin{array}{c} \aleph_1 \\ \aleph_1 \\ \aleph_1 \end{array} \right) \rightarrow \left( \begin{array}{c} \aleph_0 \\ \aleph_0 \\ \aleph_0 \end{array} \right)^{1,1,1}_2 \end{align*}$$

Mills and Prikry proved [Reference Mills and Prikry126] that

$$\begin{align*}\left( \begin{array}{c} \aleph_1 \\ \aleph_1 \\ \aleph_1 \end{array} \right) \not\rightarrow \left( \begin{array}{c} \aleph_0 \\ \aleph_0 \\ \aleph_0 \end{array} \right)^{1,1,1}_2 \end{align*}$$

and

$$\begin{align*}\left[ \begin{array}{c} \aleph_1 \\ \aleph_1 \\ \aleph_1 \end{array} \right] \rightarrow \left[ \begin{array}{c} \aleph_0 \\ \aleph_0 \\ \aleph_0 \end{array} \right]^{1,1,1}_3. \end{align*}$$

The consistency of

with can be obtained with a forcing in [Reference Shelah160]. Starting with a model of GCH, that forcing changes the value of to $\aleph _3$ with the property that each new set of ordinals of cardinality $\aleph _1$ contains an infinite old set. This easily implies the above partition relation.

Shelah proved the consistency of this for ${\lambda }=\aleph _{\omega }$ from infinitely many measurables in [Reference Shelah156], then the consistency of a stronger statement from infinitely many strongly compacts in [Reference Shelah157].

Problem 30 (GCH).

Does

$$\begin{align*}\aleph_{{\omega}+1}\not\rightarrow \left( \left( \begin{array}{c} \aleph_{{\omega}+1} \\ \aleph_{\omega} \end{array} \right), \aleph_1 \right)^2 \end{align*}$$

hold?

Problem 31. Without CH can one prove

or at least

The answer to the first question is no as $\mathrm {MA}_{{\omega }_1}$ implies ${\omega }_1\to ({\omega }_1,[{\omega }:{\omega }_1])^2$ (Laver). Szemerédi noticed that $\mathrm {MA}$ implies

(See [Reference Jones91]).

This would be a nice comment to

$$\begin{align*}\aleph_1\not\rightarrow \left( \left( \begin{array}{c} \aleph_1 \\ \aleph_0 \end{array} \right), \left( \begin{array}{c} \aleph_1 \\ \aleph_0 \end{array} \right) \right) \end{align*}$$

which follows from CH.

In [Reference Shelah152] Shelah proved the following. If $|X|={\omega }_1$ , $\mathrm {Col}(X)\leq {\omega }$ , then ${\omega }_1\to (X)^2_n$ ( $n<{\omega }$ ). On the other hand, if $\diamondsuit $ holds and X is a graph with $|X|=\mathrm {Col}(X)={\omega }_1$ , then ${\omega }_1\not \to (X)^2_2$ . There is such a graph X with $K_{\aleph _0,\aleph _1}\not \leq X$ in ZFC.

We notice that if X is a graph on ${\omega }_1$ with $\mathrm {Col}(X)={\omega }_1$ in the ground model then ${\omega }_1\not \to (X)^2_2$ holds after forcing with $\mathrm {Add}({\omega },{\omega }_1)$ . We pretend that the forcing $(P,\leq )$ is the finite coloring poset, i.e., $p\in P$ if ${\mathrm {Dom}}(p)\in [{\omega }_1]^{<{\omega }}$ , $\mathrm {Ran}(p)\subseteq 2$ , $q\leq p$ if ${\mathrm {Dom}}(q)\supseteq {\mathrm {Dom}}(p)$ and $p=q|{\mathrm {Dom}}(p)$ . Assume that p forces that $f:{\omega }_1\to {\omega }_1$ embeds X into color i. For each ${\alpha }<{\omega }_1$ let $p_{\alpha }\leq p$ fix the value of $f({\alpha })$ as $g({\alpha })$ . There is a decomposition ${\omega }_1=\bigcup \{A_j:j<{\omega }\}$ such that if ${\alpha },{\beta }\in A_j$ then $p_{\alpha }$ , $p_{\beta }$ are compatible. There is $j<{\omega }$ such that $Y=X|A_j$ has $\mathrm {Col}(Y)={\omega }_1$ . Define the set mapping $h:A_j\to [A_j]^{<{\omega }}$ by ${\beta }\in h({\alpha })$ if $g({\beta })$ is contained in some pair in ${\mathrm {Dom}}(p_{\alpha })$ . By a result of Fodor’s there are distinct ${\alpha },{\beta }\in A_j$ such that $\{{\alpha },{\beta }\}\in X$ , ${\alpha }\notin h({\beta })$ and ${\beta }\notin h({\alpha })$ , i.e., $\{g({\alpha }),g({\beta })\}$ is not in ${\mathrm {Dom}}(p_{\alpha })$ or ${\mathrm {Dom}}(p_{\beta })$ . Then there is a condition $q\leq p_{\alpha },p_{\beta }$ such that $q(g({\alpha }),g({\beta }))=1-j$ , a contradiction.

With the above argument, one can show that after adding $\aleph _2$ Cohen reals, ${\omega }_1\not \to (X)^2_2$ holds for every graph X with $|X|=\mathrm {Col}(X)={\omega }_1$ .

5 Set mappings

We denote by $({\kappa },a,b)\to {\lambda }$ if the following holds. Whenever $f:[{\kappa }]^a\to [{\kappa }]^{<b}$ is a set mapping, then there is a free set of cardinality ${\lambda }$ .

Baumgartner and independently, but later K. J. Devlin proved this in L [Reference Devlin23]. Devlin and Paris proved that if $({\kappa },<{\omega },2)\to \aleph _1$ holds for some ${\kappa }$ , then $O^\sharp $ exists. Further, if $V=L[U]$ for some normal ultrafilter U, then $({\kappa },<{\omega },2)\to {\lambda }$ iff ${\kappa }\to ({\lambda })^{<{\omega }}_2$ [Reference Devlin and Paris25].

For ${\kappa }={\omega }_{\omega }$ Koepke proved that the positive relation is equi-consistent with the existence of a measurable cardinal [Reference Koepke99].

Various people pointed out that (A) is false, as $({\kappa },<{\omega },{\lambda })\to {\kappa }$ holds if ${\kappa }$ is real valued measurable and ${\lambda }<{\kappa }$ .

For (B), Erdős and Hajnal proved $(\exp _{r-1}(\mu )^+,r,\mu )\to \mu ^+$ in [Reference Erdős and Hajnal35]. Hajnal proved that if $k<{\omega }$ , then GCH is consistent with $(\aleph _{k+2},3,2)\not \to \aleph _{k+1}$ (cf. [Reference Hajnal and Máté84]).

The following are open: Is GCH is consistent with $(\aleph _2,3,2)\to \aleph _1$ ? Is GCH is consistent with $(\aleph _3,4,2)\not \to \aleph _1$ ?

Komjáth and Shelah proved in [Reference Komjáth and Shelah107] that for $n<{\omega }$ it is consistent that $(\aleph _n,2,2)\not \to \aleph _1$ (but GCH fails).

Shelah proved in [Reference Shelah151] that if ${\kappa }$ is regular, ${\kappa }^{<{\kappa }}={\kappa }$ , is a set mapping such that for $\xi \neq \eta $ , then for every ${\alpha }<{\kappa }^+$ there is a free set of order type ${\alpha }$ .

(A) The following results have been proved.

Todorcevic extended this in [Reference Todorcevic183], Chapter 1 this to the following. If $A\subseteq \mathbb {R}$ , $|A|={\mathfrak {b}}$ , then there is , such that for any $x\in A$ , $f(x)$ is a sequence converging to x, and f has no uncountable free set.

(C) These are the corresponding results.

A family has property B, if there is a set $T\subseteq S$ , such that for every . This is equivalent to having chromatic number 2. If ${\kappa }$ is an infinite cardinal, then has property $B({\kappa })$ if there is a $T\subseteq S$ such that holds for every . Property B was introduced by E. W. Miller in [Reference Miller125], he proved that if is a system of infinite sets with () then has property B.

In [Reference Hajnal77], Hajnal gives the entertaining tale of how he and Erdős discovered Miller’s paper by accident, and realized that a new method is used in it.

In [Reference Hajnal, Juhász and Shelah82], Hajnal, Juhász, and Shelah gave a consistent counterexample from a supercompact cardinal. In [Reference Hajnal, Juhász and Shelah83], they proved the following extension of this. If GCH holds and $\mu $ is a regular cardinal with a 2-huge cardinal above it, then in a $\mu $ -closed forcing extension GCH still holds and there is an , with for such that does not have property B.

It is easy to see, that the answer is “yes” if Martin’s axiom MA holds. On the other hand, as Kunen showed in unpublished work, if ${\omega }_1$ Silver reals are added with a finite support iteration to a model with an arbitrary value of , then we obtain a model where there is a family , , does not have propert B, and is as large as wanted. Another argument was given by Baumgartner and Laver [Reference Baumgartner13]: if Sacks reals are added by a countable support iteration of length ${\omega }_2$ to a model of CH, then in the resulting model $2^{\aleph _0}=\aleph _2$ and the statement of Problem 40 is also negated.

(A) In [Reference Todorcevic183] Todorcevic proves that if on some regular cardinal ${\kappa }$ there is a nonreflecting stationary set of ${\omega }$ -limits, then there is an uncountably chromatic graph all whose smaller subgraphs are countably chromatic. In [Reference Shelah162] Shelah remarks that in the model of Ben–David and Magidor [Reference Ben-David and Magidor15] GCH holds and if $1\leq n<{\omega }$ and X is a graph with $|X|=\aleph _{{\omega }+1}$ all whose smaller subgraphs have chromatic number at most $\aleph _n$ then $\textrm {Chr}(X)\leq \aleph _n$ . That is, there is an ultrafilter D on ${\omega }_{{\omega }+1}$ such that $|{}^{{\omega }_{{\omega }+1}}{\omega }_{n}/D|=\aleph _n$ for $1\leq n<{\omega }$ and there are $A_\xi \in D$ ( $\xi <{\omega }_{{\omega }+1}$ ) with $|\{\xi :{\alpha }\in A_\xi \}|<\aleph _{\omega }$ for ${\alpha }<{\omega }_{{\omega }+1}$ . This readily implies the claimed result.

Spencer Unger proves in [Reference Unger195] that if ${\kappa }$ is supercompact and GCH holds, then in some forcing extension ${\kappa }=\aleph _{{\omega }_1}$ , GCH holds, and if $0<{\alpha }<{\omega }_1$ , X is a graph of size $\aleph _{{\omega }_1+1}$ , all whose subgraphs of size less than $\aleph _{{\omega }_1}$ have chromatic number at most $\aleph _{{\alpha }+1}$ , then $\textrm {Chr}(X)\leq \aleph _{{\alpha }+1}$ .

(B) Baumgartner showed in [Reference Baumgartner9] the consistency of the existence of a graph X with $|X|=\textrm {Chr}(X)=\aleph _2$ , such that $\textrm {Chr}(Y)\leq \aleph _0$ for each subgraph Y of smaller cardinality.

In [Reference Foreman and Laver57], Foreman and Laver proved the consistency of the statement that each graph X with $|X|=\textrm {Chr}(X)=\aleph _2$ contains a subgraph Y with $|Y|=\textrm {Chr}(Y)=\aleph _1$ (and GCH), from the consistency of a huge cardinal. Let ${\kappa }$ be huge, $j:V\to M$ an elementary embedding with $\mathrm {crit}(j)={\kappa }$ , $j({\kappa })={\lambda }$ , ${}^{\lambda } M\subseteq M$ . They construct forcing notions P and Q, such that $|P|={\kappa }$ , P is ${\kappa }$ -c.c., in $V[G_P]$ , ${\kappa }={\omega }_1$ , $Q\in V[G_P]$ is ${\lambda }$ -c.c., of cardinality ${\lambda }$ , Q is $<{\kappa }$ -closed, and ${\lambda }={\omega }_2$ in $V[G_P,G_Q]$ . Further, $j(P)$ splits as $P\ast Q\ast R$ where R is ${\kappa }$ -centred. It is fairly easy to see that the statement holds in $V[G_P,G_Q]$ (but the constructions of P and Q are involved).

In [Reference Rinot147], Rinot proved that if ${\lambda }>{\omega }$ is a cardinal, $\square _{\lambda }$ and $2^{\lambda }={\lambda }^+$ hold, ${\omega }<{\kappa }\leq {\lambda }^+$ is a cardinal, then there is a graph X on ${\lambda }^+$ such that $\mathrm {Col}(X)=\textrm {Chr}(X)={\kappa }$ and for all subgraphs Y with $|Y|\leq {\lambda }$ one has $\textrm {Chr}(Y)\leq {\omega }$ .

(A) The answer is clearly “yes” if there is a nonreflecting stationary set $S\subseteq S^{{\omega }_2}_{{\omega }}$ and CH holds, as then $\diamondsuit (S)$ holds by Gregory [Reference Gregory70].

(B) Again, a nonreflecting stationary $S\subseteq S^{{\omega }_2}_{\omega }$ gives an example. Levy collapsing a weakly compact to ${\omega }_2$ gives a model where no such graph exists and if a supercompact is collapsed to ${\omega }_2$ then every graph X with $\mathrm {Col}(X)>{\omega }_1$ contains a subgraph Y with $|Y|=\mathrm {Col}(Y)={\omega }_1$ .

(C) Let $\mathrm {PT}({\lambda })$ denote the statement that if is a ${\lambda }$ -sized family of sets of cardinality $\aleph _0$ , each , has a transversal, then so has .

From a nonreflecting stationary subset of $S^{{\omega }_2}_{\omega }$ one can find an example witnessing $\neg \mathrm {PT}({\omega }_2)$ . This is in fact true in ZFC, the example given by J. Truss is where $F_{{\alpha },{\beta }}={\alpha }\times \{{\alpha },{\beta }\}$ . This was extended by Milner and Shelah, showing that $\neg \mathrm {PT}({\lambda })$ implies $\neg \mathrm {PT}({\lambda }^+)$ [Reference Milner and Shelah131]. Shelah then proved that if $\aleph _{{\omega }}$ is strong limit, then $\neg \mathrm {PT}(\aleph _{{\omega }+1})$ holds [Reference Shelah155].

In a remarkable paper Shelah proved that $\mathrm {PT}({\lambda })$ holds for each singular ${\lambda }$ [Reference Shelah154]. This holds for the coloring number and a large class of other notions.

In [Reference Magidor and Shelah123], Magidor and Shelah proved $\neg \mathrm {PT}(\aleph _{{\omega }+1})$ without any extra assumption. From the consistency of ${\omega }$ supercompact cardinals, they proved $\mathrm {PT}(\aleph _{{\omega }^2+1})$ consistent, and they also proved (from the same assumption) that the following is consistent: if ${\lambda }$ is the first cardinal fixed point, then ${\lambda }$ is fully compact, i.e., if is a system of sets of cardinality $\aleph _0$ , , with no transversal, then there is a subfamily , , with no transversals, either.

Baumgartner noticed that an easy construction gives a function as wanted. Let $f:{\omega }_1-\{0\}\to {\omega }_1$ be a regressive function such that if $\gamma =0$ or limit, then for every ${\beta }<\gamma +{\omega }$ the set $\{\max ({\beta },\gamma )<{\alpha }<\gamma +{\omega }:f({\alpha })={\beta }\}$ is infinite. A function like this can easily be constructed and it is equally easy to see that it is as required.

In [Reference Hajnal76], Hajnal shows using CH that there is a graph X on ${\omega }^2_1$ , which is triangle-free, omits $K_{\aleph _0,\aleph _0}$ , and has no independent set of type ${\omega }^2_1$ . The latter obviously implies $\textrm {Chr}(X)=\aleph _1$ .

(A) Komjáth and Shelah proved that consistently there is a graph X with $|X|=\textrm {Chr}(X)=\aleph _1$ all whose triangle-free subgraphs are countably chromatic [Reference Komjáth and Shelah105].

(B) This was proved by Rödl [Reference Rödl148].

Erdős suggested a more general conjecture, namely, if $3\leq n<{\omega }$ , the chromatic number of X is $\aleph _0$ , then there is a subgraph Y of X, with $\textrm {Chr}(Y)=\aleph _0$ and Y omittings circuits of length $3,4,\dots ,n$ (see, e.g., in [Reference Erdős34]).

This was proved independently by Erdős–Hajnal–Shelah [Reference Erdős, Hajnal and Shelah49] and Thomassen [Reference Thomassen179].

Problem 47. Let X be a graph with $\textrm {Chr}(X)=\aleph _0$ , N the set of lengths of circuits contained in X, does

$$\begin{align*}\sum_{i\in N}\frac{1}{i}=\infty \end{align*}$$

hold?

Gyárfás, Komlós, and Szemerédi proved that for any finite graph this sum is at least $c\log k$ , where k is the least degree and $k\geq k_0$ for some value $k_0$ [Reference Gyárfás, Komlós and Szemerédi71]. As by the Erdős–de Bruijn theorem a graph with chromatic number $\aleph _0$ contains finite subgraphs with arbitrarily large finite chromatic number, which in turn contain finite subgraphs with arbitrarily large minimal degree (in a minimal graph of chromatic number k each degree is at least $k-1$ ), the statement follows.

An extension given also by Erdős and Hajnal has recently been solved by Liu and Montgomery, who proved that if $\textrm {Chr}(X)=k$ , then

$$\begin{align*}\sum_{n\in N,n\equiv 1\ \pmod{2}}\frac{1}{n}\geq \left(\frac{1}{2}-o_k(1)\right)\log k \end{align*}$$

(see [Reference Liu and Montgomery121]).

In fact, they prove that for some $d_0>0$ , if X is a finite graph with average degree $d\geq d_0$ , then there is some $k\geq d/(10 \log ^{10} d)$ , such that N contains all even integers in $[\log ^8 k,k]$ .

Shelah proved in [Reference Shelah152] that, if V=L holds, ${\kappa }>{\omega }$ is regular, not weakly compact, then there is a graph X with $|X|={\kappa }$ , $\mathrm {Col}(X)>{\omega }$ , such that for each subgraph Y with $|Y|<{\kappa }$ , one has $\mathrm {Col}(Y)\leq {\omega }$ .

The complementary independence result is proved by Komjáth: if $\mu <{\kappa }$ , ${\kappa }$ is weakly compact (supercompact) then in some model ${\kappa }=\mu ^{++}$ and for every graph X of cardinality ${\kappa }$ (of any cardinality) if every subgraph Y of X with $|Y|<{\kappa }$ has $\mathrm {Col}(Y)\leq \mu $ , then $\mathrm {Col}(X)\leq \mu $ [Reference Komjáth100].

In [Reference Lambie-Hanson and Rinot113] Lambie–Hanson and Rinot proved that if $\mu <{\kappa }$ , ${\kappa }$ is regular, X is a graph on ${\kappa }$ with $\mathrm {Col}(Y)\leq \mu $ for each $Y\leq X$ with $|Y|<{\kappa }$ , then

1. (a) $\mathrm {Col}(X)\leq \mu ^+$ , unless ${\kappa }={\lambda }^+$ , $\textrm {cf}({\lambda })=\textrm {cf}(\mu )$ ,

2. (b) $\mathrm {Col}(X)\leq \mu ^{++}$ anyway.

Further, if X is a graph on ${\omega }_{{\omega }+1}$ whose all smaller subgraphs have countable coloring number and the Chang conjecture $(\aleph _{{\omega }+1},\aleph _{\omega })\twoheadrightarrow (\aleph _1,\aleph _0)$ holds, then $\mathrm {Col}(X)\leq {\omega }_1$ .

In [Reference Erdős and Hajnal38], Erdős and Hajnal proved that if X is an infinite graph, $1\leq k<{\omega }$ , each finite subgraph Y has $\mathrm {Col}(Y)\leq k$ , then $\mathrm {Col}(X)\leq 2k-1$ . This is sharp in the sense that for each $n<{\omega }$ there is a graph X of size $\aleph _n$ with each smaller subgraph Y having $\mathrm {Col}(Y)\leq k$ , but $\mathrm {Col}(X)\leq 2k-1$ . The problem asks if there is a similar example of size $\aleph _{{\omega }+1}$ . These results show that the Erdős–de Bruijn theorem holds for the coloring number in a weaker form.

Shelah in [Reference Shelah152] proved the following.

The consistency of (d) was then proved by Hajnal, Juhász, and Shelah in [Reference Hajnal, Juhász and Shelah82] from the consistency of the existence of a supercompact.

The relevance of is that no graph of cardinality may have those properties as is the union of $\aleph _0$ bipartite graphs. For more comments see Problem 53.

Shelah proved the consistency of the existence of such a graph in [Reference Shelah161]. The existence of a graph like this in ZFC is open. In [Reference Komjáth and Shelah106], Komjáth and Shelah gave the consistency of the following. If X is a graph, $\mu $ a cardinal, then there is a graph Y such that $Y\to (X)^2_\mu $ and if $K_{\alpha }\not \leq X$ , then $K_{\alpha }\not \leq Y$ .

Erdős and Hajnal remarked that if ${\kappa }$ is infinite, then there is a graph X omitting $K_{(2^{\kappa })^+}$ with $X\to ({\kappa }^+)^2_{\kappa }$ : $(2^{\kappa })^+\not \to ((2^{\kappa })^+,(2^{\kappa })^+)^2$ and $(2^{\kappa })^+\to \left ((2^{\kappa })^+,({\kappa }^+)^2_{\kappa }\right )^2$ . If X consists of the edges of color 1 in the coloring witnessing the first example, then we are done.

In [Reference Komjáth101], I modified this as follows. Given ${\kappa }$ , let ${\lambda }$ be such that ${\lambda }^{\kappa }<{\lambda }^{{\kappa }^+}$ (e.g., ${\lambda }=\exp _{{\kappa }^+}({\kappa })$ ). Then partition theory gives ${\lambda }^+\to \left ({\lambda }^+,({\kappa }^+)_{\kappa }\right )^2$ (Erdős–Rado) and ${\lambda }^{{\kappa }^+}\not \to ({\lambda }^+,{\kappa }^{++})^2$ . By the condition imposed on ${\lambda }$ , we also have ${\lambda }^+\not \to ({\lambda }^+,{\kappa }^{++})^2$ . If X is the graph of the edges of color 1 in the latter example, then $K_{{\kappa }^{++}}\not \leq X$ and $X\to ({\kappa }^+)^2_{\kappa }$ .

An example for the simplest interesting case, $n=2$ , $k=3$ was given by Jon Folkman in [Reference Folkman54]. His proof was specific for the values of $n,k$ and the given graph had a stellar number of vertices.

Erdős asked repeteadly if there is a significatly smaller such graph, with, say, less than $10^{10}$ vertices. Frankl and Rödl constructed an example with roughly $10^{11}$ vertices. In the years around 2000 this was first decreased to around 10,000 by L. Lu, then to 941 by Dudek and Rödl [Reference Dudek and Rödl27], then to 786 by Lange, Radziszowski, and Xu in [Reference Lange, Radziszowski and Xu114].

The general case was then proved by Nesteril and Rödl, in fact, they proved that if Y is a finite graph containing no $K_{k+1}$ , $r<{\omega }$ , then there is a finite graph X omitting $K_{k+1}$ such that if the edges of X are colored with r colors, then there is a monocolored, induced copy of Y [Reference Nesteril and Rödl134, Reference Nesetril and Rödl135].

Amazingly, there are pure existence proofs of graphs asked in the problem. One is given Shelah’s consistent existence of a graph as in Problem 53 [Reference Shelah161]. Namely, that graph X has the (weaker) property that, if the edges are colored with 2 colors, then always exists a monocolored triangle. By compactness, there is a finite subgraph Y of X with this property. As by forcing no finite graph can be added, Y is already in the ground model.

For the Folkman case there is an even trickier argument. In [Reference Baumgartner and Hajnal11] Baumgartner and Hajnal proved that $\omega ^2_1\to (\omega _1\omega ,3,3)^2$ , and under CH, the relation $\omega ^2_1\not \to (\omega _1\omega ,4)^2$ holds. The proof of the second statement is relatively straightforward, that of the first one is quite complicated. The second statement can be reformulated as follows. There is a $K_4$ -free graph X on ${\omega }^2_1$ with no independent set of type ${\omega }_1{\omega }$ . By the first theorem each such graph has the property that under any 2-coloring of the edges there is a monochromatic triangle. Again, then X is a $K_4$ -free graph having monochromatic triangles in any 2-colorings of the edges, by compactness X has a finite subgraph Y with similar properties. So, Y exists in any model of CH. As CH can be added by forcing, each model has a forcing extension having the above Y, and then each model must have it. Hajnal was very proud of this argument all his life.

It is unknown if $\omega ^2_1\to (\omega _1\omega ,3,3,3)^2$ holds or at least if it is consistent that ${\alpha }\not \to ({\beta },4)^2$ and ${\alpha }\to ({\beta },3,3,3)^2$ , for some ordinals ${\alpha },{\beta }$ .

In order to formulate the following problem, we write $a\to [b,c]^d_e$ if the following holds. If , , then either there is $S\in [a]^b$ , such that for every $X\in [S]^d$ , there is an , $X\subseteq A$ , or else there is $T\in [a]^c$ , , , .

These problems were raised in [Reference Erdős, Hajnal and Milner46]. In [Reference Erdős and Hajnal42] Erdős and Hajnal mention that (B) and (C) can be proved relatively easily. I proved that (A) is false, i.e., GCH is consistent with the negation of the statement in (A) with $a=\aleph _2$ [Reference Komjáth103].

In [Reference Erdős and Hajnal37] Erdős and Hajnal considered the following problem. Let ${\kappa }$ be a cardinal, f a function on $[{\kappa }]^k$ with $f(s)$ a Lebesgue measurable subset of $[0,1]$ , ${\lambda }(f(s))\geq u$ . Is there a subset $A\in [{\kappa }]^\mu $ with $\bigcap \{f(s):s\in [A]^k\}\neq \emptyset $ ? We write $({\kappa },u)^k\to \mu $ if the answer is ‘yes’.

This is solved in [Reference Galvin and Prikry65].

Problem 59. Does

$$\begin{align*}\left( \begin{array}{c} \aleph_0 \\ \aleph_1 \end{array} \right) \rightarrow \left( \begin{array}{cc} 1 & \aleph_0 \\ 4 & \aleph_0 \end{array} \right)^{1,2} \end{align*}$$

hold?

Problem 60. Does

$$\begin{align*}\left( \begin{array}{c} \aleph_1 \\ \aleph_0 \end{array} \right) \rightarrow \left( \begin{array}{cc} 1 & \aleph_0 \\ \aleph_0 & \aleph_0 \end{array} \right)^{1,2} \end{align*}$$

hold?

As Erdős and Hajnal remarked in [Reference Erdős and Hajnal42], CH implies a “yes” answer. In [Reference Komjáth102] we give this (unpublished) result and show that Martin’s axiom implies a “no” answer.

We say that a set system posesses property $B(a,b)$ if for every , $b'<b$ , there is with .

$(m,n)\to (a,b)$ denotes the statement that the Cartesian product of two systems with $B(a,b)$ has $B(m,n)$ .

Problem 63. Let $3\leq r<{\omega }$ . Does

$$\begin{align*}(\exp_{r-1}(\aleph_0),r+1)\not\to(\aleph_1,\aleph_0) \end{align*}$$

or

$$\begin{align*}(\exp_{r-1}(\aleph_0),r+1)\not\to(\aleph_1,\aleph_1) \end{align*}$$

hold?

As it was remarked in [Reference Erdős and Hajnal42], this follows immediately from

$$\begin{align*}\left( \begin{array}{c} {\omega}_1 \\ {\omega}^2 \end{array} \right) \rightarrow \left( \begin{array}{c} {\omega} \\ {\omega}^2 \end{array} \right)^{1,1}_{2}. \end{align*}$$

of [Reference Baumgartner and Hajnal10].

Laver gave an affirmative answer to this. He also proved that if $\phi $ is a $\sigma $ -scattered order type, i.e., $\phi \not \to (\eta )^1_{\aleph _0}$ , then $\phi \to [\phi ]^1_n$ holds for some $n<{\omega }$ [Reference Laver118].

Raised in [Reference Erdős and Hajnal39]. In [Reference Hajnal78], Hajnal attributes this beautiful question to Erdős.

Shelah in [Reference Shelah153] proved that CH gives a counterexample. In fact, this is an easy application of the existence of a Lusin set.

Shelah also proved, that if V=L, then for every regular cardinal ${\kappa }$ , there is a function $F:[{\kappa }^+]^2\to {\kappa }^+$ witnessing ${\kappa }^+\not \to [{\kappa }^+]^2_{{\kappa }^+}$ with no triangles of three colors. Todorcevic in [Reference Todorcevic180] extended this to all regular, not weakly compact cardinals.

In [Reference Komjáth102] I proved that a ${\kappa }$ -Suslin tree implies the existence of a function $F:[{\kappa }]^2\to {\kappa }$ witnessing ${\kappa }\not \to [{\kappa }]^2_{\kappa }$ with no 3-colored triangles. On the other hand, if such a coloring exists, then there is a ${\kappa }$ -Aronszajn tree.

Erdős asked the following finite version of the problem. Is there an $\varepsilon>0$ such that the following holds? If $F:[n]^2\to 3$ is such that in every $A\subseteq n$ , $|A|\geq n^\varepsilon $ , all three colors occur, does then F necessarily contain a 3-colored triangle? This was answered by Shelah in [Reference Shelah153] with the value $\varepsilon =1/12$ . The bound was improved by Fox, Grinshpun, and Pach in [Reference Fox, Grinshpun and Pach60] to $|A|\geq n^{1/3}\log ^2 n$ and this, apart from a constant, is sharp.

In [Reference Komjáth102] I proved that both this statement and its negation are consistent.

If $\langle V,X\rangle $ is a graph, a set system, we say that -represents X iff there is a bijection such that

Erdős and Hajnal proved that if ${\kappa }$ is regular, then every graph with at most ${\kappa }^+$ vertices can be ${\kappa }$ -represented by some .

The above mentioned regular case was finally published in [Reference Erdős, Milner and Rado51, Lemma 6].

Let A be a set and . Let $a=\{a_\xi :\xi <\phi \}$ be a set of elements of A. We say that strongly cuts a if for each $\xi <\phi $ there is an such that .

In [Reference Erdős and Makkai50] Erdős and Makkai proved that if A is infinite, , then there is a sequence of type ${\omega }$ which is either strongly cut by or is strongly cut by the set of complements of .

Concerning (A), Shelah proved that for every infinite cardinal ${\lambda }$ there is a set S, $|S|={\lambda }$ , and a set system with no sequences $a=\{a_i:i<{\omega }\}\subseteq S$ and such that ( $i<{\omega }$ ). Shelah further proved that, if GCH holds, $|A|={\kappa }^{+3}$ , , , then there is a sequence of elements of A, of length ${\kappa }^+$ , which is strongly cut either by or by the set of complements in [Reference Shelah150].

As for (B), one can easily see that if $\binom {\aleph _2}{\aleph _1}\not \to \binom {\aleph _0}{\aleph _1}^{1,1}_2$ holds, then there is a set system , so that no sequence of length ${\omega }_1$ is strongly cut by or by the set of complements of (cf. Prikry’s result in Problem 24).

The same holds if CH fails by an easy construction. Namely, if is an almost disjoint set system, , then establishes that (B) fails with $\xi ={\omega }+2$ . The consistency of the positive statement is not known.

This extends a result in [Reference Erdős and Hajnal36], that for every $F:[{\omega }_1]^2\to k$ (k finite) there is a monocolored topological $K_{\aleph _1}$ . In [Reference Erdős and Hajnal42] Erdős and Hajnal notice that the comparison graph of a Suslin tree is a counterexample. Komjáth and Shelah in [Reference Komjáth and Shelah108] prove that the statement holds exactly if there is no Suslin tree. They further prove that the statement that if $F:[{\omega }_2]^2\to {\omega }$ , then there is a monocolored topological $K_{\aleph _2}$ is both consistent and independent.

Recently, a paper by Bergfalk, Hrušák, and Shelah considers a similar problem: if ${\kappa }$ is an infinite cardinal, $F:[{\kappa }]^2\to \mu $ , is there a monocolored ${\kappa }$ -connected graph [Reference Bergfalk17]? It is easy to see that a yes answer gives a monochromatic topological $K_{\kappa }$ .

The answer is “yes”, if $\mu $ is finite, by the proof of Erdős–Hajnal [Reference Erdős and Hajnal36]. If ${\kappa }=\aleph _2$ , $\mu =\aleph _0$ , both answers are consistent. Bergfalk, Hrusák, and Shelah also deduce a negative answer from a form of $\square $ , considered by Todorcevic. Finally, they prove that if ${\lambda }^{\kappa }={\lambda }$ , $F:[{\lambda }^+]^2\to {\kappa }$ , then there is a ${\lambda }$ -connected, monochromatic subgraph of size ${\lambda }$ .

The affirmative answer (based on the existence of a ${\kappa }$ -Aronszajn tree) was given by Erdős and Hajnal in [Reference Erdős and Hajnal43].

This was answered in the affirmative by Shelah in [Reference Shelah151] for any singular cardinal in place of $\aleph _{\omega }$ . Next, Komjáth and Pach discussed under GCH when a universal graph of cardinality ${\kappa }$ omitting $K_{n,{\lambda }}$ (n finite, ${\omega }\leq {\lambda }\leq {\kappa }$ ) exists [Reference Komjáth and Pach104]. Finally, in [Reference Shelah169], Shelah completely settled (again under GCH) when a universal $K_{{\alpha },{\beta }}$ -omitting graph of size ${\kappa }$ exists.

Shelah remarked that an ${\omega }_1$ -descendingly complete uniform ultrafilter on ${\omega }_{\omega }$ gives a counterexample.

Problem 76 (Erdős).

If is an uncountable cardinal, can there be a set of ${\kappa }$ entire functions, such that

holds for every $a\in \mathbb {C}$ ?

This was asked by J. Wetzel for ${\kappa }=\aleph _1$ . It is easy to see that an affirmative answer can only hold for . Erdős proved that the ${\kappa }=\aleph _1$ case is equivalent to the continuum hypothesis [Reference Erdős33].

Erdős’s problem has recently been settled by Kumar and Shelah in [Reference Kumar and Shelah110]. First they show that a “no” answer is consistent with any possible value of with . In fact, this holds if $\aleph _1$ Cohen reals are added to a model of . The proof utilizes the fact that a nonzero entire function cannot have more roots in a larger universe. Then they prove that a “yes” answer is consistent with .

In [Reference Hajnal and Juhász79] Hajnal and Juhász proved that a Hausdorff space with no discrete subspace of cardinality $>{\kappa }$ has at most $2^{2^{\kappa }}$ points. In [Reference Todorcevic182], Todorcevic showed the consistency of the statement that if a Hausdorff space does not contain uncountable discrete subspaces then it has at most points.

Jensen proved that a tree with certain properties, whose existence follows from $V=L$ , implies a counterexample. In [Reference Fleissner53], Fleissner gives Jensen’s argument and further proves that such a tree can be constructed from an ${\omega }_2$ -Suslin-tree.

Juhász and Shelah in [Reference Juhász and Shelah93] prove the following result. Assume GCH and that $\aleph _1<{\lambda }<\mu $ are regular cardinals. Then in some cardinal preserving extension , $2^{\lambda }=\mu $ , and there is a hereditarily separable Hausdorff space $X\subseteq {}^{\lambda } 2$ , $|X|=\mu $ . Todorcevic proved in [Reference Todorcevic182] that PFA implies a NO answer.

Hajnal and Juhász announced in [Reference Hajnal and Juhász80] and published in [Reference Hajnal and Juhász81] the consistency of a “yes” answer. They formulated a combinatorial statement implying the existence of a space as required and then gave a forcing proof for the consistency of the statement. In [Reference Kanamori94], Kanamori shows that the statement follows from Silver’s principle W, holding in L.