Erdős and Rado proved that $\mathfrak{c}\to (\omega+n,4)_2^3$ for any $2\leq n<\omega$.

View the LaTeX source

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 conjectured that this can be improved to $\ll n^{1+\epsilon}$ for every $\epsilon>0$.

See also [74].

View the LaTeX source

Such $\alpha$ are called partition ordinals. 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.

See also [590], [591], and [592] for more on partition ordinals.

View the LaTeX source

This page was last edited 17 January 2026.

A problem of Erdős from 1954. Sierpinski and Kurepa independently proved that this is true for $2$-colours. Erdős proved that this is true under the continuum hypothesis that $\mathfrak{c}=\aleph_1$, and offered \$100 for deciding what happens if the continuum hypothesis is not assumed.

Shelah proved that it is consistent that the answer is negative, although with a very large value of $\mathfrak{c}$. It remains open whether it is consistent to have a negative answer assuming $\mathfrak{c}=\aleph_2$.

View the LaTeX source

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

Gladysz [Gl62] proved the existence of an independent set of size $2$ under the assumptions of the the second question.

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

Newelski, Pawlikowski, and Seredyński [NPS87] proved the answer to the first question is yes, under the additional assumption that the $A_x$ are closed.

View the LaTeX source

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$ (a question of Erdős for which he offered \$20).

This is true, and was proved by Chang [Ch72]. Milner modified Chang's 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].

View the LaTeX source

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]).

This is true and was proved independently by Schipperus [Sc10] and Darby.

See also [118], and [592] for the general case.

View the LaTeX source

This page was last edited 17 January 2026.

Such $\alpha$ are called partition ordinals.

• Specker [Sp57] proved this holds for $\beta=2$ and not for $3\leq \beta <\omega$.


• Chang [Ch72] proved this holds for $\beta=\omega$.


• 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 countable ordinal $\gamma$. Galvin and Larson conjecture that every $\beta\geq 3$ of this form has this property.


• Schipperus [Sc10] have proved this is holds if $\beta=\omega^\gamma$ in which $\gamma$ is a countable ordinal which is the sum of one or two indecomposable ordinals, and this fails to hold if $\gamma$ is the sum of four or more indecomposable ordinals.

The remaining open case appears to be when $\gamma$ is the sum of three indecomposable ordinals.

The case $\beta=\omega$ is the subject of [590], and $\beta=\omega^2$ is the subject of [591]. See also [118].

View the LaTeX source

This page was last edited 17 January 2026.

Similar problems were investigated by Erdős, Galvin, and Hajnal [EGH75]. Erdős claims that for graphs the problem is completely solved: a graph of chromatic number $\geq \aleph_1$ must contain all finite bipartite graphs but need not contain any fixed odd cycle.

View the LaTeX source

A problem of Erdős and Hajnal (who proved this for chromatic number $\geq \aleph_2$). This was proved by Erdős, Hajnal, and Shelah [EHS74].

See also [593] and [737].

View the LaTeX source

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.

See also [582] and [596].

View the LaTeX source

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].

View the LaTeX source

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$.

View the LaTeX source

View the LaTeX source

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].

View the LaTeX source

A problem of Erdős, Hajnal, and Milner [EHM70], who proved this is true for $\alpha < \omega_1^{\omega+2}$.

In [Er82e] Erdős offers \$250 for showing what happens when $\alpha=\omega_1^{\omega+2}$ and \$500 for settling the general case.

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

View the LaTeX source

A problem of Komjáth. The existence of such a $2$-colouring is sometimes known as Property B.

View the LaTeX source

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.

View the LaTeX source

This page was last edited 28 December 2025.

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'.

View the LaTeX source

A question of Erdős and Hajnal. We say a graph is infinitely connected if any two vertices are connected by infinitely many pairwise disjoint paths.

Komjáth [Ko13] proved that it is consistent that the answer is no. This was improved by Soukup [So15], who constructed a counterexample using no extra set-theoretical assumptions. A simpler elementary example was given by Bowler and Pitz [BoPi24].

Thomassen [Th17] constructed a counterexample to the version which asks for infinite edge-connectivity (that is, to disconnect the graph requires deleting infinitely many edges).

In [ErHa66] Erdős and Hajnal asked the same question under the additional assumption that the graph has $\aleph_1$ many vertices. Komjáth [Ko13] proved that the answer is independent of ZFC.

See also [1068].

View the LaTeX source

This page was last edited 18 January 2026.

I do not think this was originally a question of Erdős - it appears in [BoPi24] as a 'version of the Erdős-Hajnal problem' (which is [1067]).

I could not in fact find this in the paper of Erdős and Hajnal [ErHa66], however, and hence the first place it appears may in fact be in [BoPi24]. In hindsight this should not have been included as a separate problem, but this has been discovered too late, and so we must leave it here.

We say a graph is infinitely (vertex) connected if any two vertices are connected by infinitely many pairwise vertex-disjoint paths.

Soukup [So15] constructed a graph with uncountable chromatic number in which every uncountable set is finitely vertex-connected. A simpler construction was given by Bowler and Pitz [BoPi24].

See also [1067].

View the LaTeX source

This page was last edited 18 January 2026.

This is Problem 2.46 in [Ha74], where it is attributed to Erdős.

Erdős [Er64g] proved (answering a question of Wetzel) that if there are only countably many distinct values for each $f_\alpha(z_0)$ then, if $\mathfrak{c}>\aleph_1$, the family $\{f_\alpha\}$ is itself countable, and also showed this is false if $\mathfrak{c}=\aleph_1$.

In [Ha74] it is written that it is 'easy to see' the answer is yes if $\mathfrak{m}^+<\mathfrak{c}$, and also that it is possible that the question is undecidable.

Indeed, it has been shown that this is undecidable if $\mathfrak{m}^+=\mathfrak{c}$: Kumar and Shelah [KuSh17] have shown that there is a model in which $\mathfrak{c}=\aleph_2$ such that the answer is yes (with $\mathfrak{m}=\aleph_1$), while Schilhan and Weinert [ScWe24] have shown the answer can be no, in a different model with $\mathfrak{c}=\aleph_2$.

View the LaTeX source

This page was last edited 31 December 2025.

This is true (assuming the continuum hypothesis) when $n=1$, since Erdős and Kakutani [ErKa43] proved that in fact the continuum hypothesis is equivalent to the statemant that $\mathbb{R}$ can be written as the union of countably many sets, each of which is linearly independent over $\mathbb{Q}$.

Davies [Da72] proved this true when $n=2$, and Kunen [Ku87] proved it is true for all $n$ (again, both assuming the continuum hypothesis).

The dependence on the continuum hypothesis is necessary, since Erdős and Hajnal proved that if the continuum hypothesis is false then e.g. in any decomposition of $\mathbb{R}$ into finitely many sets there exist four points which determine only four distances.

View the LaTeX source

This page was last edited 30 December 2025.

A problem of Erdős and Hajnal.

This was disproved by Prikry and Mills in 1978 but this seems to have been unpublished. This is reported by Todorčević [To94] and Komjáth [Ko25b].

View the LaTeX source

This page was last edited 30 December 2025.