Logo
All Random Solved Random Open
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.)

See also the entry in the graphs problem collection.

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

Additional thanks to: Tuan Tran
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].

See also the entry in the graphs problem collection.

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

See also [74].

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.

See also the entry in the graphs problem collection.

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