5 solved out of 20 shown (show only solved or open)
SOLVED - $500 If$G$is an edge-disjoint union of$n$copies of$K_n$then is$\chi(G)=n$? Conjectured by Faber, Lovász, and Erdős. Kahn [Ka92] proved that$\chi(G)\leq (1+o(1))n$. Hindman has proved the conjecture for$n<10$. Kang, Kelly, Kühn, Methuku, and Osthus [KKKMO21] have proved the answer is yes for all sufficiently large$n$. In [Er97d] Erdős asks how large$\chi(G)$can be if instead of asking for the copies of$K_n$to be edge disjoint we only ask for their intersections to be triangle free, or to contain at most one edge. OPEN -$1000
Let $f(n,k)$ be minimal such that every $\mathcal{F}$ family of $n$-uniform sets with $\lvert F\rvert \geq f(n,k)$ contains a $k$-sunflower. Is it true that $f(n,k) < c_k^n$ for some constant $c_k>0$?
Erdős and Rado [ErRa60] originally proved $f(n,k)\leq (k-1)^nn!$. Kostochka [Ko97] improved this slightly (in particular establishing an upper bound of $o(n!)$, for which Erdős awarded him the consolation prize of \$100), but the bound stood at$n^{(1+o(1))n}$for a long time until Alweiss, Lovett, Wu, and Zhang [ALWZ20] proved $f(n,k) < (Ck\log n\log\log n)^n$ for some constant$C>1$. This was refined slightly, independently by Rao [Ra20], Frankston, Kahn, Narayanan, and Park [FKNP19], and Bell, Chueluecha, and Warnke [BCW21], leading to the current record of $f(n,k) < (Ck\log n)^n$ for some constant$C>1$. The usual focus is on the regime where$k=O(1)$is fixed (say$k=3$) and$n$is large, although for the opposite regime Kostochka, Rödl, and Talysheva [KoRoTa99] have shown $f(n,k)=(1+O_n(k^{-1/2^n}))k^n.$ Additional thanks to: Zachary Chase SOLVED Let$k\geq 0$. Let$G$be a graph on$n$vertices such that every subgraph$H\subseteq G$contains an independent set of size$\geq \frac{1}{2}\lvert H\rvert-k$. Must$G$be the union of a bipartite graph and$O_k(1)$many vertices? Proved by Reed [Re99]. (Thanks also to Reed for pointing out that the case$k=0$is trivial, since if$G$is not bipartite then$G$contains an odd cycle.) 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. 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]).
SOLVED
Is it true that in any $2$-colouring of the edges of $K_n$ there must exist at least $(1+o(1))\frac{n^2}{12}$ many edge-disjoint monochromatic triangles?
Conjectured by Erdős, Faudreee, and Ordman. This would be best possible, as witnessed by dividing the vertices of $K_n$ into two equal parts and colouring all edges between the parts red and all edges inside the parts blue.

The answer is yes, proved by Gruslys and Letzter [GrLe20].

In [Er97d] Erdős also asks for a lower bound for the count of edge-disjoint monochromatic triangles in single colour (the colour chosen to maximise this quantity), and speculates that the answer is $\geq cn^2$ for some constant $c?1/24$.

OPEN - $250 Find the value of$\lim_{k\to \infty}R(k)^{1/k}$. Erdős offered \$100 for just a proof of the existence of this constant, without determining its value. He also offered \$1000 for a proof that the limit does not exist, but says 'this is really a joke as [it] certainly exists'. Erdős proved $\sqrt{2}\leq \liminf_{k\to \infty}R(k)^{1/k}\leq \limsup_{k\to \infty}R(k)^{1/k}\leq 4.$ The upper bound has been improved to$4-\tfrac{1}{128}$by Campos, Griffiths, Morris, and Sahasrabudhe [CGMS23]. OPEN Let$F(n)$be maximal such that every graph on$n$vertices contains a regular induced subgraph on at least$F(n)$vertices. Prove that$F(n)/\log n\to \infty$. Conjectured by Erdős, Fajtlowicz, and Stanton. It is known that$F(5)=3$and$F(7)=4$. Ramsey's theorem implies that$F(n)\gg \log n$. Bollobás observed that$F(n)\ll n^{1/2+o(1)}$. Alon, Krivelevich, and Sudakov [AKS07] have improved this to$n^{1/2}(\log n)^{O(1)}$. Additional thanks to: Zachary Hunter SOLVED The cycle set of a graph$G$on$n$vertices is a set$A\subseteq \{3,\ldots,n\}$such that there is a cycle in$G$of length$\ell$if and only if$\ell \in A$. Let$f(n)$count the number of possible such$A$. Prove that$f(n)=o(2^n)$. Conjectured by Erdős and Faudree, who showed that$f(n) > 2^{n/2}$, and further speculate that$f(n)/2^{n/2}\to \infty$. This conjecture was proved by Verstraëte [Ve04], who proved the number of such sets is $\ll 2^{n-n^c}$ for some constant$c>0$. There are interesting further questions (including$f(n)2^{-n/2}\to \infty$and the existence of$\lim f(n)^{1/n}$) which remain open. Additional thanks to: Tuan Tran SOLVED -$100
For any $\epsilon>0$ there exists $\delta=\delta(\epsilon)>0$ such that if $G$ is a graph on $n$ vertices with no independent set or clique of size $\geq \epsilon\log n$ then $G$ contains an induced subgraph with $m$ edges for all $m\leq \delta n^2$.
Conjectured by Erdős and McKay, who proved it with $\delta n^2$ replaced by $\delta (\log n)^2$. Solved by Kwan, Sah, Sauermann, and Sawhney [KSSS22]. Erdős' original formulation also had the condition that $G$ has $\gg n^2$ edges, but an old result of Erdős and Szemerédi says that this follows from the other condition anyway.
Additional thanks to: Zachary Hunter and Mehtaab Sawhney
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}$.

OPEN
Let $G$ be a graph with $n$ vertices and at least $n^2/4$ edges. Are there at least $2n^2/9$ edges of $G$ which are contained in a $C_5$?
Erdős [Er97d] stated that, under the same assumptions, there at least $2n^2/9$ edges of $G$ which are contained in some odd cycle. He wrote that a positive answer to this question would follow if we knew that $G$ must contain a triangle such that there at least $n/2-O(1)$ vertices joined to at least two vertices of the triangle.

Erdős and Faudree observed that every graph with $2n$ vertices and at least $n^2+1$ edges has a triangle whose vertices are joined to at least $n+2$ vertices.

OPEN
Suppose $G$ is a graph on $n$ vertices which contains no complete graph or independent set on $\gg \log n$ many vertices. Must $G$ contain $\gg n^{5/2}$ induced subgraphs which pairwise differ in either the number of vertices or the number of edges?
A problem of Erdős, Faudree, and Sós, who proved there exist $\gg n^{3/2}$ many such subgraphs, and note that $n^{5/2}$ would be best possible.
OPEN
If $G$ is a graph on $n$ vertices which contains no complete graph or independent set on $\gg \log n$ vertices then $G$ contains an induced subgraph on $\gg n$ vertices which contains $\gg n^{1/2}$ distinct degrees.
A problem of Erdős, Faudree, and Sós.
OPEN
Let $S$ be a family of finite graphs such that for every $n$ there is some $G_n\in S$ such that if the edges of $G_n$ are coloured with $n$ colours then there is a monochromatic triangle.

Is it true that for every infinite cardinal $\aleph$ there is a graph $G$ of which every finite subgraph is in $S$ and if the edges of $G$ are coloured with $\aleph$ many colours then there is a monochromatic triangle.

Erdős writes 'if the answer is affirmative many extensions and generalisations will be possible'.
OPEN
Is it true that if the edges of $K_n$ are 2-coloured then there are at most $n^2/4$ many edges which do not occur in a monochromatic triangle?
A problem of Erdős, Rousseau, and Schelp.
OPEN
Is there some function $f$ such that for all $k\geq 3$ if a finite graph $G$ has chromatic number $\geq f(k)$ then $G$ must contain some odd cycle whose vertices span a graph of chromatic number $\geq k$?
A problem of Erdős and Hajnal.
OPEN
Is there some function $f$ such that for all $k\geq 1$ if a finite graph $G$ has chromatic number $\geq f(k)$ then $G$ has $k$ edge disjoint cycles on the same set of vertices?
A problem of Erdős and Hajnal.
OPEN
Is there some constant $C$ such that any graph $G$ on $n$ vertices with $\geq Cn$ edges must contain a cycle which has at least as many diagonals as vertices?
A problem of Hamburger and Szegedy.
OPEN
Let $f(n;t)$ be minimal such that if a $t$-uniform hypergraph on $n$ vertices contains at least $f(n;t)$ edges then there must be four edges $A,B,C,D$ such that $A\cup B= C\cup D$ and $A\cap B=C\cap D=\emptyset.$ Estimate $f(n;t)$ - in particular, is it true that for $t\geq 3$ $f(n;t)=(1+o(1))\binom{n}{t-1}?$
For $n=2$ this is asking for the maximal number of edges on a graph which contains no $C_4$, and so $f(n;2)=(1+o(1))n^{3/2}$.

Füredi proved that $f(n;3) \ll n^2$ and $f(n;3) > \binom{n}{2}$ for infinitely many $n$. More generally, Füredi proved that $f(n;t) \ll \binom{n}{t-1}.$

OPEN
Let $f(k,r)$ be minimal such that if $A_1,A_2,\ldots$ is a family of sets, all of size $k$, such that for every collection of $r$ of the $A_is$ there is some pair $\{x,y\}$ which intersects all of the $A_j$, then there is some set of size $f(k,r)$ which intersects all of the sets $A_i$. Is it true that $f(k,7)=(1+o(1))\frac{3}{4}k?$ Is it true that for any $r\geq 3$ there exists some constant $c_r$ such that $f(k,r)=(1+o(1))c_rk?$
A problem of Erdős, Fon-Der-Flaass, Kostochka, and Tuza [EFKT92], who proved that $f(k,3)=2k$ and $f(k,4)=\lfloor 3k/2\rfloor$ and $f(k,5)=\lfloor 5k/4\rfloor$, and further that $f(k,6)=k$.