2 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 - $500 Let$f(n)\to \infty$(possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on$n$vertices can be made bipartite by deleting at most$f(n)$edges? Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. Rödl [Ro82] has proved this for hypergraphs, and also proved there is such a graph (with chromatic number$\aleph_0$) if$f(n)=\epsilon n$for any fixed constant$\epsilon>0$. It is open even for$f(n)=\sqrt{n}$. Erdős offered \$500 for a proof but only \$250 for a counterexample. This fails (even with$f(n)\gg n$) if the graph has chromatic number$\aleph_1$(see [111]). OPEN Let$c>0$and let$f_c(n)$be the maximal$m$such that every graph$G$with$n$vertices and at least$cn^2$edges, where each edge is contained in at least one triangle, must contain an edge in at least$m$different triangles. Estimate$f_c(n)$. In particular, is it true that$f_c(n)>n^{\epsilon}$for some$\epsilon>0$? Or even$f_c(n)\gg \log n$? A problem of Erdős and Rothschild. Alon and Trotter showed that$f_c(n)\ll_c n^{1/2}$. Szemerédi observed that his regularity lemma implies that$f_c(n)\to \infty$. See also [600] and the entry in the graphs problem collection. OPEN Is there some$F(n)$such that every graph with chromatic number$\aleph_1$has, for all large$n$, a subgraph with chromatic number$n$on at most$F(n)$vertices? Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. This fails if the graph has chromatic number$\aleph_0$. 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$. See also [74]. 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 -$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. 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, Nešetřil, and Rödl 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 (so Erdős writes, but I cannot find the reference).

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
Let $e(n,r)$ be minimal such that every graph on $n$ vertices with at least $e(n,r)$ edges, each edge contained in at least one triangle, must have an edge contained in at least $r$ triangles. Let $r\geq 2$. Is it true that $e(n,r+1)-e(n,r)\to \infty$ as $n\to \infty$? Is it true that $\frac{e(n,r+1)}{e(n,r)}\to 1$ as $n\to \infty$?
Ruzsa and Szemerédi [RuSz78] proved that $e(n,r)=o(n^2)$ for any fixed $r$.

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