4 solved out of 18 shown (show only solved or open)
OPEN
Let $\mathfrak{c}$ be the ordinal of the real numbers, $\beta$ be any countable ordinal, and $2\leq n<\omega$. Is it true that $\mathfrak{c}\to (\beta, n)_2^3$?
Erdős and Rado proved that $\mathfrak{c}\to (\omega+n,4)_2^3$ for any $2\leq n<\omega$.
OPEN
If $G$ is a graph let $h_G(n)$ be defined such that any subgraph of $G$ on $n$ vertices can be made bipartite after deleting at most $h_G(n)$ edges.

What is the behaviour of $h_G(n)$? Is it true that $h_G(n)/n\to \infty$ for every graph $G$ with chromatic number $\aleph_1$?

A problem of Erdős, Hajnal, and Szemerédi [EHS82]. Every $G$ with chromatic number $\aleph_1$ must have $h_G(n)\gg n$ since $G$ must contain, for some $r$, $\aleph_1$ many vertex disjoint odd cycles of length $2r+1$.

On the other hand, Erdős, Hajnal, and Szemerédi proved that there is a $G$ with chromatic number $\aleph_1$ such that $h_G(n)\ll n^{3/2}$. In [Er81] Erdős conjectures that this can be improved to $\ll n^{1+\epsilon}$ for every $\epsilon>0$.

SOLVED
Let $\alpha$ be a cardinal or ordinal number or an order type such that every two-colouring of $K_\alpha$ contains either a red $K_\alpha$ or a blue $K_3$. For every $n\geq 3$ must every two-colouring of $K_\alpha$ contain either a red $K_\alpha$ or a blue $K_n$?
Conjectured by Erdős and Hajnal. In arrow notation, this is asking where $\alpha \to (\alpha,3)^2$ implies $\alpha \to (\alpha, n)^2$ for every finite $n$.

The answer is no, as independently shown by Schipperus [Sc99] (published in [Sc10]) and Darby [Da99].

For example, Larson [La00] has shown that this is false when $\alpha=\omega^{\omega^2}$ and $n=5$. There is more background and proof sketches in Chapter 2.9 of [HST10], by Hajnal and Larson.

Additional thanks to: Zachary Chase, Andrés Caicedo
OPEN
For every $x\in\mathbb{R}$ let $A_x\subset \mathbb{R}$ be a bounded set with outer measure $<1$. Must there exist an infinite independent set, that is, some infinite $X\subseteq \mathbb{R}$ such that $x\not\in A_y$ for all $x\neq y\in X$?

If the sets $A_x$ are closed and have measure $<1$, then must there exist an independent set of size $3$?

Erdős and Hajnal [ErHa60] proved the existence of arbitrarily large finite independent sets (under the assumptions in the first problem).

Erdős writes in [Er61] that Gladysz has proved the existence of an independent set of size $2$ in the second question, but I cannot find a reference.

Hechler [He72] has shown the answer to the first question is no, assuming the continuum hypothesis.

SOLVED - $250 Let$\alpha$be the infinite ordinal$\omega^\omega$. Is it true that in any red/blue colouring of the edges of$K_\alpha$there is either a red$K_\alpha$or a blue$K_3$? A problem of Erdős and Rado. For comparison, Specker [Sp57] proved this property holds when$\alpha=\omega^2$and false when$\alpha=\omega^n$for$3\leq n<\omega$. This is true, and was proved by Chang [Ch72]. Milner modified his proof to prove that this remains true if we replace$K_3$by$K_m$for all finite$m<\omega$(a shorter proof was found by Larson [La73]). See also [591] and [592]. OPEN -$250
Let $\alpha$ be the infinite ordinal $\omega^{\omega^2}$. Is it true that in any red/blue colouring of the edges of $K_\alpha$ there is either a red $K_\alpha$ or a blue $K_3$?
For comparison, Specker [Sp57] proved this property holds when $\alpha=\omega^2$ and false when $\alpha=\omega^n$ for $3\leq n<\omega$. Chang proved this property holds when $\alpha=\omega^\omega$ (see [590]).

See [592] for the general case.

OPEN - $1000 Determine which countable ordinals$\beta$have the property that, if$\alpha=\omega^{^\beta}$, then in any red/blue colouring of the edges of$K_\alpha$there is either a red$K_\alpha$or a blue$K_3$. This property holds for$\beta=2$and not for$3\leq \beta <\omega$(Specker [Sp57]) and for$\beta=\omega$(Chang [Ch72]). The first open case is$\beta=\omega^2$(see [591]). Galvin and Larson [GaLa74] have shown that if$\beta\geq 3$has this property then$\beta$must be 'additively indecomposable', so that in particular$\beta=\omega^\gamma$for some$\gamma<\omega_1$. Galvin and Larson conjecture that every$\beta\geq 3$of this form has this property. See also [590]. OPEN Let$G_1$and$G_2$be two graphs with chromatic number$\aleph_1$. Must there be a graph$H$with chromatic number$4$which appears as a subgraph of both$G_1$and$G_2$? Is there such an$H$with chromatic number$\aleph_0$? Erdős also asks about finding a common subgraph$H$(with chromatic number either$4$or$\aleph_0$) in any finite collection of graphs with chromatic number$\aleph_1$. Every graph with chromatic number$\aleph_1$contains all sufficiently large odd cycles (which have chromatic number$3$), see [594]. This was proved by Erdős, Hajnal, and Shelah [EHS74]. Erdős writes that 'probably' every graph with chromatic number$\aleph_1$contains as subgraphs all graphs with chromatic number$4$with sufficiently large girth. SOLVED Does every graph$G$with chromatic number$\geq \aleph_1$contain all sufficiently large odd cycles? A problem of Erdős and Hajnal. This was proved by Erdős, Hajnal, and Shelah [EHS74]. See also [593] and [737]. OPEN -$250
Is there an infinite graph $G$ which contains no $K_4$ and is not the union of countably many triangle-free graphs?
A problem of Erdős and Hajnal. Folkman [Fo70] and Nešetřil and Rödl [NeRo75] have proved that for every $n\geq 1$ there is a graph $G$ which contains no $K_4$ and is not the union of $n$ triangle-free graphs.

OPEN
For which graphs $G_1,G_2$ is it true that
• for every $n\geq 1$ there is a graph $H$ without a $G_1$ but if the edges of $H$ are $n$-coloured then there is a monochromatic copy of $G_2$, and yet
• for every graph $H$ without a $G_1$ there is an $\aleph_0$-colouring of the edges of $H$ without a monochromatic $G_2$.
Erdős and Hajnal originally conjectured that there are no such $G_1,G_2$, but in fact $G_1=C_4$ and $G_2=C_6$ is an example. Indeed, for this pair Nešetřil and Rödl established the first property and Erdős and Hajnal the second (in fact every $C_4$-free graph is a countable union of trees).

Whether this is true for $G_1=K_4$ and $G_2=K_3$ is the content of [595].

OPEN
Let $G$ be a graph on at most $\aleph_1$ vertices which contains no $K_4$ and no $K_{\aleph_0,\aleph_0}$ (the complete bipartite graph with $\aleph_0$ vertices in each class). Is it true that $\omega_1^2 \to (\omega_1\omega, G)^2?$ What about finite $G$?
Erdős and Hajnal proved that $\omega_1^2 \to (\omega_1\omega,3)^2$. Erdős originally asked this with just the assumption that $G$ is $K_4$-free, but Baumgartner proved that $\omega_1^2 \not\to (\omega_1\omega, K_{\aleph_0,\aleph_0})^2$.
OPEN
Let $m$ be an infinite cardinal and $\kappa$ be the successor cardinal of $2^{\aleph_0}$. Can one colour the countable subsets of $m$ using $\kappa$ many colours so that every $X\subseteq m$ with $\lvert X\rvert=\kappa$ contains subsets of all possible colours?
SOLVED
Let $G$ be a (possibly infinite) graph and $A,B$ be disjoint independent sets of vertices. Must there exist a family $P$ of disjoint paths between $A$ and $B$ and a set $S$ which contains exactly one vertex from each path in $P$, and such that every path between $A$ and $B$ contains at least one vertex from $S$?
Sometimes known as the Erdős-Menger conjecture. When $G$ is finite this is equivalent to Menger's theorem. Erdős was interested in the case when $G$ is infinite.

This was proved by Aharoni and Berger [AhBe09].

OPEN
For which limit ordinals $\alpha$ is it true that if $G$ is a graph with vertex set $\alpha$ then $G$ must have either an infinite path or independent set on a set of vertices with order type $\alpha$?
A problem of Erdős, Hajnal, and Milner [EHM70], who proved this is true for $\alpha < \omega_1^{\omega+2}$.

Larson [La90] proved this is true for all $\alpha<2^{\aleph_0}$ assuming Martin's axiom.

OPEN
Let $(A_i)$ be a family of sets with $\lvert A_i\rvert=\aleph_0$ for all $i$, such that for any $i\neq j$ we have $\lvert A_i\cap A_j\rvert$ finite and $\neq 1$. Is there a $2$-colouring of $\cup A_i$ such that no $A_i$ is monochromatic?
A problem of Komjáth. The existence of such a $2$-colouring is sometimes known as Property B.
OPEN
Let $(A_i)$ be a family of countable sets such that $\lvert A_i\cap A_j\rvert \neq 2$ for all $i\neq j$. Is there some $C$ such that $\cup A_i$ can always be coloured with at most $C$ colours so that no $A_i$ is monochromatic?
A problem of Komjáth. If instead we have $\lvert A_i\cap A_j\rvert \neq 1$ then Komjáth showed that this is possible with at most $\aleph_0$ colours.
OPEN
Let $X$ be a set of cardinality $\aleph_\omega$ and $f$ be a function from the finite subsets of $X$ to $X$ such that $f(A)\not\in A$ for all $A$. Must there exist an infinite $Y\subseteq X$ that is independent - that is, for all finite $B\subset Y$ we have $f(B)\not\in Y$?
A problem of Erdős and Hajnal [ErHa58], who proved that if $\lvert X\rvert <\aleph_\omega$ then the answer is no. Erdős suggests in [Er99] that this problem is 'perhaps undecidable'.