OPEN - $500

If $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ then
\[N \gg 2^{n}.\]

Erdős called this 'perhaps my first serious problem'. The powers of $2$ show that $2^n$ would be best possible here. The trivial lower bound is $N \gg 2^{n}/n$, since all $2^n$ distinct subset sums must lie in $[0,Nn)$. Erdős and Moser [Er56] proved
\[ N\geq (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.\]
A number of improvements of the constant have been given (see [St23] for a history), with the current record $\sqrt{2/\pi}$ first proved in unpublished work of Elkies and Gleason. Two proofs achieving this constant are provided by Dubroff, Fox, and Xu [DFX21], who in fact prove the exact bound $N\geq \binom{n}{\lfloor n/2\rfloor}$.

In [Er73] and [ErGr80] the generalisation where $A\subseteq (0,N]$ is a set of real numbers such that the subset sums all differ by at least $1$ is proposed, with the same conjectured bound. (The second proof of [DFX21] applies also to this generalisation.)

This problem appears in Erdős' book with Spencer [ErSp74] in the final chapter titled 'The kitchen sink'. As Ruzsa writes in [Ru99] "it is a rich kitchen where such things go to the sink".

See also [350].

OPEN - $5000

If $A\subseteq \mathbb{N}$ has $\sum_{n\in A}\frac{1}{n}=\infty$ then must $A$ contain arbitrarily long arithmetic progressions?

This is essentially asking for good bounds on $r_k(N)$, the size of the largest subset of $\{1,\ldots,N\}$ without a non-trivial $k$-term arithmetic progression. For example, a bound like
\[r_k(N) \ll_k \frac{N}{(\log N)(\log\log N)^2}\]
would be sufficient.

Even the case $k=3$ is non-trivial, but was proved by Bloom and Sisask [BlSi20]. Much better bounds for $r_3(N)$ were subsequently proved by Kelley and Meka [KeMe23]. Green and Tao [GrTa17] proved $r_4(N)\ll N/(\log N)^{c}$ for some small constant $c>0$. Gowers [Go01] proved \[r_k(N) \ll \frac{N}{(\log\log N)^{c_k}},\] where $c_k>0$ is a small constant depending on $k$. The current best bounds for general $k$ are due to Leng, Sah, and Sawhney [LSS24], who show that \[r_k(N) \ll \frac{N}{\exp((\log\log N)^{c_k})}\] for some constant $c_k>0$ depending on $k$.

Curiously, Erdős [Er83c] thought this conjecture was the 'only way to approach' the conjecture that there are arbitrarily long arithmetic progressions of prime numbers, now a theorem due to Green and Tao [GrTa08].

In [Er81] Erdős makes the stronger conjecture that \[r_k(N) \ll_C\frac{N}{(\log N)^C}\] for every $C>0$ (now known for $k=3$ due to Kelley and Meka [KeMe23]) - see [140].

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 (apparently 'at a party in Boulder, Colarado in September 1972' [Er81]).

Kahn [Ka92] proved that $\chi(G)\leq (1+o(1))n$ (for which Erdős gave him a 'consolation prize' of \$100). 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$.

In [Er81] offered \$1000 for a proof or disproof even just in the special case when $k=3$, which he expected 'contains the whole difficulty'. He also wrote 'I really do not see why this question is so difficult'.

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

SOLVED - $500

Let $f(n)$ be minimal such that there is an intersecting family $\mathcal{F}$ of sets of size $n$ (so $A\cap B\neq\emptyset$ for all $A,B\in \mathcal{F}$) with $\lvert \mathcal{F}\rvert=f(n)$ such that any set $S$ with $\lvert S\rvert \leq n-1$ is disjoint from at least one $A\in \mathcal{F}$.

Is it true that \[f(n) \ll n?\]

Conjectured by Erdős and Lovász [ErLo75], who proved that
\[\frac{8}{3}n-3\leq f(n) \ll n^{3/2}\log n\]
for all $n$. The upper bound was improved by Kahn [Ka92b] to
\[f(n) \ll n\log n.\]
(The upper bound constructions in both cases are formed by taking a random set of lines from a projective plane of order $n-1$, assuming $n-1$ is a prime power.)

This problem was solved by Kahn [Ka94] who proved the upper bound $f(n) \ll n$. The Erdős-Lovász lower bound of $\frac{8}{3}n-O(1)$ has not been improved, and it has been speculated (see e.g. [Ka94]) that the correct answer is $3n+O(1)$.

In [Er97f] Erdős asks about $f_\epsilon(n)$, defined analogously except with $\lvert S\rvert \leq n-1$ replaced by $\lvert S\rvert \leq (1-\epsilon)n$. He asks whether $f_\epsilon(n)/n\to \infty$ as $\epsilon \to 0$.

OPEN - $500

If $A\subseteq \mathbb{N}$ is such that $A+A$ contains all but finitely many integers then $\limsup 1_A\ast 1_A(n)=\infty$.

Conjectured by Erdős and Turán. They also suggest the stronger conjecture that $\limsup 1_A\ast 1_A(n)/\log n>0$.

Another stronger conjecture would be that the hypothesis $\lvert A\cap [1,N]\rvert \gg N^{1/2}$ for all large $N$ suffices.

Erdős and Sárközy conjectured the stronger version that if $A=\{a_1<a_2<\cdots\}$ and $B=\{b_1<b_2<\cdots\}$ with $a_n/b_n\to 1$ are such that $A+B=\mathbb{N}$ then $\limsup 1_A\ast 1_B(n)=\infty$.

See also [40].

OPEN - $1000

Let $h(N)$ be the maximum size of a Sidon set in $\{1,\ldots,N\}$. Is it true that, for every $\epsilon>0$,
\[h(N) = N^{1/2}+O_\epsilon(N^\epsilon)?\]

A problem of Erdős and Turán. It may even be true that $h(N)=N^{1/2}+O(1)$, but Erdős remarks this is perhaps too optimistic. Erdős and Turán [ErTu41] proved an upper bound of $N^{1/2}+O(N^{1/4})$, with an alternative proof by Lindström [Li69]. Both proofs in fact give
\[h(N) \leq N^{1/2}+N^{1/4}+1.\]
Balogh, Füredi, and Roy [BFR21] improved the bound in the error term to $0.998N^{1/4}$, which has been further optimised by O'Bryant [OB22] to yield
\[h(N)\leq N^{1/2}+0.99703N^{1/4}\]
for sufficiently large $N$.

See also [241].

OPEN - $500

Is there an infinite Sidon set $A\subset \mathbb{N}$ such that
\[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\]
for all $\epsilon>0$?

The trivial greedy construction achieves $\gg N^{1/3}$. The current best bound of $\gg N^{\sqrt{2}-1+o(1)}$ is due to Ruzsa [Ru98]. (Erdős [Er73] had offered \$25 for any construction which achieves $N^{c}$ for some $c>1/3$.) Erdős proved that for every infinite Sidon set $A$ we have
\[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0,\]
and also that there is a set $A\subset \mathbb{N}$ with $\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}$ such that $1_A\ast 1_A(n)=O(1)$.

Erdős and Rényi have constructed, for any $\epsilon>0$, a set $A$ such that \[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\] for all large $N$ and $1_A\ast 1_A(n)\ll_\epsilon 1$ for all $n$.

OPEN - $500

Let $A\subset\mathbb{N}$ be an infinite set such that the triple sums $a+b+c$ are all distinct for $a,b,c\in A$ (aside from the trivial coincidences). Is it true that
\[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/3}}=0?\]

Erdős proved that if the pairwise sums $a+b$ are all distinct aside from the trivial coincidences then
\[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0.\]

SOLVED

If $G$ is a graph with infinite chromatic number and $a_1<a_2<\cdots $ are lengths of the odd cycles of $G$ then $\sum \frac{1}{a_i}=\infty$.

OPEN

Let $G$ be a graph with $n$ vertices and $kn$ edges, and $a_1<a_2<\cdots $ be the lengths of cycles in $G$. Is it true that
\[\sum\frac{1}{a_i}\gg \log k?\]
Is the sum $\sum\frac{1}{a_i}$ minimised when $G$ is a complete bipartite graph?

A problem of Erdős and Hajnal. Gyárfás, Komlós, and Szemerédi [GyKoSz84] have proved that this sum is $\gg \log k$. Liu and Montgomery [LiMo20] have proved the asymptotically sharp lower bound of $\geq (\tfrac{1}{2}-o(1))\log k$.

See also the entry in the graphs problem collection.

See also [57].

SOLVED - $500

If $f:\mathbb{N}\to \{-1,+1\}$ then is it true that for every $C>0$ there exist $d,m\geq 1$ such that
\[\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert > C?\]

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

This problem is #3 in Ramsey Theory in the graphs problem collection.

OPEN - $500

Does every set of $n$ distinct points in $\mathbb{R}^2$ determine $\gg n/\sqrt{\log n}$ many distinct distances?

A $\sqrt{n}\times\sqrt{n}$ integer grid shows that this would be the best possible. Nearly solved by Guth and Katz [GuKa15] who proved that there are always $\gg n/\log n$ many distinct distances.

A stronger form (see [604]) may be true: is there a single point which determines $\gg n/\sqrt{\log n}$ distinct distances, or even $\gg n$ many such points, or even that this is true averaged over all points.

See also [661].

OPEN - $500

Does every set of $n$ distinct points in $\mathbb{R}^2$ contain at most $n^{1+O(1/\log\log n)}$ many pairs which are distance 1 apart?

The unit distance problem. In [Er94b] Erdős dates this conjecture to 1946.

This would be the best possible, as is shown by a set of lattice points. It is easy to show that there are $O(n^{3/2})$ many such pairs. The best known upper bound is $O(n^{4/3})$, due to Spencer, Szemerédi, and Trotter [SST84]. In [Er83c] and [Er85] Erdős offers \$250 for an upper bound of the form $n^{1+o(1)}$.

Part of the difficulty of this problem is explained by a result of Valtr (see [Sz16]), who constructed a metric on $\mathbb{R}^2$ and a set of $n$ points with $\gg n^{4/3}$ unit distance pairs (with respect to this metric). The methods of the upper bound proof of Spencer, Szemerédi, and Trotter [SST84] generalise to include this metric. Therefore to prove an upper bound better than $n^{4/3}$ some special feature of the Euclidean metric must be exploited.

See a survey by Szemerédi [Sz16] for further background and related results.

OPEN - $500

Let $f(n)$ be minimal such that any $f(n)$ points in $\mathbb{R}^2$, no three on a line, contain $n$ points which form the vertices of a convex $n$-gon. Prove that $f(n)=2^{n-2}+1$.

The Erdős-Klein-Szekeres 'Happy Ending' problem. The problem originated in 1931 when Klein observed that $f(4)=5$. Turán and Makai showed $f(5)=9$. Erdős and Szekeres proved the bounds
\[2^{n-2}+1\leq f(n)\leq \binom{2n-4}{n-2}+1.\]
([ErSz60] and [ErSz35] respectively). There were several improvements of the upper bound, but all of the form $4^{(1+o(1))n}$, until Suk [Su17] proved
\[f(n) \leq 2^{(1+o(1))n}.\]
The current best bound is due to Holmsen, Mojarrad, Pach, and Tardos [HMPT20], who prove
\[f(n) \leq 2^{n+O(\sqrt{n\log n})}.\]

In [Er97e] Erdős clarifies that the \$500 is for a proof, and only offers \$100 for a disproof.

This problem is #1 in Ramsey Theory in the graphs problem collection.

OPEN

For every $r\geq 4$ and $k\geq 2$ is there some finite $f(k,r)$ such that every graph of chromatic number $\geq f(k,r)$ contains a subgraph of girth $\geq r$ and chromatic number $\geq k$?

Conjectured by Erdős and Hajnal. Rödl [Ro77] has proved the $r=4$ case. The infinite version (whether every graph of infinite chromatic number contains a subgraph of infinite chromatic number whose girth is $>k$) is also open.

In [Er79b] Erdős also asks whether \[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]

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

OPEN

Let the van der Waerden number $W(k)$ be such that whenever $N\geq W(k)$ and $\{1,\ldots,N\}$ is $2$-coloured there must exist a monochromatic $k$-term arithmetic progression. Improve the bounds for $W(k)$ - for example, prove that $W(k)^{1/k}\to \infty$.

SOLVED - $1000

Let $r_k(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $k$-term arithmetic progression. Prove that $r_k(N)=o(N)$.

Proved by Szemerédi [Sz74]. The best known bounds are due to Kelley and Meka [KeMe23] for $k=3$ (with further slight improvements in [BlSi23]), Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$.

See also [3].

SOLVED - $500

Let $r_3(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $3$-term arithmetic progression. Prove that $r_3(N)\ll N/(\log N)^C$ for every $C>0$.

OPEN - $10000

Let $r_k(N)$ be the largest possible size of a subset of $\{1,\ldots,N\}$ that does not contain any non-trivial $k$-term arithmetic progression. Prove an asymptotic formula for $r_k(N)$.

Erdős remarked this is 'probably unattackable at present'. In [Er97c] Erdős offered \$1000, but given that he elsewhere offered \$5000 just for (essentially) showing that $r_k(N)=o_k(N/\log N)$, that value seems odd. In [Er81] he offers \$10000, stating it is 'probably enormously difficult'.

The best known upper bounds for $r_k(N)$ are due to Kelley and Meka [KeMe23] for $k=3$, Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$. An asymptotic formula is still far out of reach, even for $k=3$.

The current bounds are
\[ \frac{n^{3/2}}{(\log n)^{3/2}}\ll R(C_4,K_n)\ll \frac{n^2}{(\log n)^2}.\]
The upper bound is due to Szemerédi (mentioned in [EFRS78]), and the lower bound is due to Spencer [Sp77].

This problem is #17 in Ramsey Theory in the graphs problem collection.

SOLVED

Let $k\geq 3$. What is the maximum number of edges that a graph on $n$ vertices can contain if it does not have a $k$-regular subgraph? Is it $\ll n^{1+o(1)}$?

Asked by Erdős and Sauer. Resolved by Janzer and Sudakov [JaSu22], who proved that there exists some $C=C(k)>0$ such that any graph on $n$ vertices with at least $Cn\log\log n$ edges contains a $k$-regular subgraph.

A construction due to Pyber, Rödl, and Szemerédi [PRS95] shows that this is best possible.

OPEN

Any graph on $n$ vertices can be decomposed into $O(n)$ many cycles and edges.

SOLVED

Let $C>0$ be arbitrary. Is it true that, if $n$ is sufficiently large depending on $C$, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and
\[\sum_{x\in X}\frac{1}{\log x}\geq C?\]

The answer is yes, which was proved by Rödl [Ro03].

In the same article Rödl also proved a lower bound for this problem, constructing, for all $n$, a $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ such that if $X\subseteq \{2,\ldots,n\}$ is such that $\binom{X}{2}$ is monochromatic then \[\sum_{x\in X}\frac{1}{\log x}\ll \log\log\log n.\]

This bound is best possible, as proved by Conlon, Fox, and Sudakov [CFS13], who proved that, if $n$ is sufficiently large, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and \[\sum_{x\in X}\frac{1}{\log x}\geq 2^{-8}\log\log\log n.\]

SOLVED

Let $f(n)$ be minimal such that the following holds. For any $n$ points in $\mathbb{R}^2$, not all on a line, there must be at least $f(n)$ many lines which contain exactly 2 points (called 'ordinary lines'). Does $f(n)\to \infty$? How fast?

Conjectured by Erdős and de Bruijn. The Sylvester-Gallai theorem states that $f(n)\geq 1$. The fact that $f(n)\geq 1$ was conjectured by Sylvester in 1893. Erdős rediscovered this conjecture in 1933 and told it to Gallai who proved it.

That $f(n)\to \infty$ was proved by Motzkin [Mo51]. Kelly and Moser [KeMo58] proved that $f(n)\geq\tfrac{3}{7}n$ for all $n$. This is best possible for $n=7$. Motzkin conjectured that for $n\geq 13$ there are at least $n/2$ such lines. Csima and Sawyer [CsSa93] proved a lower bound of $f(n)\geq \tfrac{6}{13}n$ when $n\geq 8$. Green and Tao [GrTa13] proved that $f(n)\geq n/2$ for sufficiently large $n$. (A proof that $f(n)\geq n/2$ for large $n$ was earlier claimed by Hansen but this proof was flawed.)

The bound of $n/2$ is best possible for even $n$, since one could take $n/2$ points on a circle and $n/2$ points at infinity. Surprisingly, Green and Tao [GrTa13] show that if $n$ is odd then $f(n)\geq 3\lfloor n/4\rfloor$.

SOLVED - $100

Let $1\leq k<n$. Given $n$ points in $\mathbb{R}^2$, at most $n-k$ on any line, there are $\gg kn$ many lines which contain at least two points.

In particular, given any $2n$ points with at most $n$ on a line there are $\gg n^2$ many lines formed by the points. Solved by Beck [Be83] and Szemerédi and Trotter [SzTr83].

In [Er84] Erdős speculates that perhaps there are $\geq (1+o(1))kn/6$ many such lines, but says 'perhaps [this] is too optimistic and one should first look for a counterexample'. The constant $1/6$ would be best possible here, since there are arrangements of $n$ points with no four points on a line and $\sim n^2/6$ many lines containing three points (see Burr, Grünbaum, and Sloane [BGS74] and Füredi and Palásti [FuPa84]).

SOLVED

Let $g(k)$ be the smallest integer (if any such exists) such that any $g(k)$ points in $\mathbb{R}^2$ contains an empty convex $k$-gon (i.e. with no point in the interior). Does $g(k)$ exist? If so, estimate $g(k)$.

A variant of the 'happy ending' problem [107], which asks for the same without the 'no point in the interior' restriction. Erdős observed $g(4)=5$ (as with the happy ending problem) but Harborth [Ha78] showed $g(5)=10$. Nicolás [Ni07] and Gerken [Ge08] independently showed that $g(6)$ exists. Horton [Ho83] showed that $g(n)$ does not exist for $n\geq 7$.

This problem is #2 in Ramsey Theory in the graphs problem collection.

SOLVED

Let $M=(a_{ij})$ be a real $n\times n$ doubly stochastic matrix (i.e. the entries are non-negative and each column and row sums to $1$). Does there exist some $\sigma\in S_n$ such that
\[\prod_{1\leq i\leq n}a_{i\sigma(i)}\geq n^{-n}?\]

A weaker form of the conjecture of van der Waerden, which states that
\[\mathrm{perm}(M)=\sum_{\sigma\in S_n}\prod_{1\leq i\leq n}a_{i\sigma(i)}\geq n^{-n}n!\]
with equality if and only if $a_{ij}=1/n$ for all $i,j$.

This conjecture is true, and was proved by Marcus and Minc [MaMi62].

Erdős also conjectured the even weaker fact that there exists some $\sigma\in S_n$ such that $a_{i\sigma(i)}\neq 0$ for all $i$ and \[\sum_{i}a_{i\sigma(i)}\geq 1.\] This weaker statement was proved by Marcus and Ree [MaRe59].

van der Waerden's conjecture itself was proved by Gyires [Gy80], Egorychev [Eg81], and Falikman [Fa81].

OPEN - $500

What is $\mathrm{ex}_3(n,K_4^3)$? That is, the largest number of $3$-edges which can placed on $n$ vertices so that there exists no $K_4^3$, a set of 4 vertices which is covered by all 4 possible $3$-edges.

A problem of Turán. Turán observed that dividing the vertices into three equal parts $X_1,X_2,X_3$, and taking the edges to be those triples that either have exactly one vertex in each part or two vertices in $X_i$ and one vertex in $X_{i+1}$ (where $X_4=X_1$) shows that
\[\mathrm{ex}_3(n,K_4^3)\geq\left(\frac{5}{9}+o(1)\right)\binom{n}{3}.\]
This is probably the truth. The current best upper bound is
\[\mathrm{ex}_3(n,K_4^3)\leq 0.5611666\binom{n}{3},\]
due to Razborov [Ra10].

See also [712] for the general case.

OPEN

What is the chromatic number of the plane? That is, what is the smallest number of colours required to colour $\mathbb{R}^2$ such that no two points of the same colour are distance $1$ apart?

The Hadwiger-Nelson problem. Let $\chi$ be the chromatic number of the plane. An equilateral triangle trivially shows that $\chi\geq 3$. There are several small graphs that show $\chi\geq 4$ (in particular the Moser spindle and Golomb graph). The best bounds currently known are
\[5 \leq \chi \leq 7.\]
The lower bound is due to de Grey [dG18]. The upper bound can be seen by colouring the plane by tesselating by hexagons with diameter slightly less than $1$.

SOLVED

Let $R(G;3)$ denote the minimal $m$ such that if the edges of $K_m$ are $3$-coloured then there must be a monochromatic copy of $G$. Show that
\[R(C_n;3) \leq 4n-3.\]

A problem of Bondy and Erdős. This inequality is best possible for odd $n$.

Luczak [Lu99] has shown that $R(C_n;3)\leq (4+o(1))n$ for all $n$, and in fact $R(C_n;3)\leq 3n+o(n)$ for even $n$.

Kohayakawa, Simonovits, and Skokan [KSS05] proved this conjecture when $n$ is sufficiently large and odd. Benevides and Skokan [BeSk09] proved that if $n$ is sufficiently large and even then $R(C_n;3)=2n$.

OPEN - $500

Let $R_3(n)$ be the minimal $m$ such that if the edges of the $3$-uniform hypergraph on $m$ vertices are $2$-coloured then there is a monochromatic copy of the complete $3$-uniform hypergraph on $n$ vertices.

Is there some constant $c>0$ such that \[R_3(n) \geq 2^{2^{cn}}?\]

OPEN

Show that for any rational $\alpha \in (1,2)$ there exists a bipartite graph $G$ such that
\[\mathrm{ex}(n;G)\asymp n^{\alpha}.\]
Conversely, if $G$ is bipartite then must there exist some rational $\alpha$ such that\[\mathrm{ex}(n;G)\asymp n^{\alpha}?\]

A problem of Erdős and Simonovits.

See also [713] and the entry in the graphs problem collection.

OPEN

Let $Q_k$ be the $k$-dimensional hypercube graph (so that $Q_k$ has $2^k$ vertices and $k2^{k-1}$ edges). Determine the behaviour of
\[\mathrm{ex}(n;Q_k).\]

Erdős and Simonovits [ErSi70] proved that
\[(\tfrac{1}{2}+o(1))n^{3/2}\leq \mathrm{ex}(n;Q_3) \ll n^{8/5}.\]
In [Er81] Erdős asks whether it is $\asymp n^{8/5}$.

A theorem of Sudakov and Tomon [SuTo22] implies \[\mathrm{ex}(n;Q_k)=o(n^{2-\frac{1}{k}}).\] Janzer and Sudakov [JaSu22b] have improved this to \[\mathrm{ex}(n;Q_k)\ll_k n^{2-\frac{1}{k-1}+\frac{1}{(k-1)2^{k-1}}}.\] See also the entry in the graphs problem collection.

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 $c<1$ be some constant and $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ be such that $\lvert A_i\rvert >c\sqrt{n}$ for all $i$ and $\lvert A_i\cap A_j\rvert\leq 1$ for all $i\neq j$.

Must there exist some set $B$ such that $B\cap A_i\neq \emptyset$ and $\lvert B\cap A_i\rvert \ll_c 1$ for all $i$?

This would imply in particular that in a finite geometry there is always a blocking set which meets every line in $O(1)$ many points.

In [Er81] the condition $\lvert A_i\cap A_j\rvert\leq 1$ for all $i\neq j$ is replaced by every two points in $\{1,\ldots,n\}$ being contained in exactly one $A_i$, that is, $A_1,\ldots,A_m$ is a pairwise balanced block design (and the condition $c<1$ is omitted).

OPEN

Let $\mathcal{F}$ be a family of sets closed under taking subsets (i.e. if $B\subseteq A\in\mathcal{F}$ then $B\in \mathcal{F}$). There exists some element $x$ such that whenever $\mathcal{F}'\subseteq \mathcal{F}$ is an intersecting subfamily we have
\[\lvert \mathcal{F}'\rvert \leq \lvert \{ A\in \mathcal{F} : x\in A\}\rvert.\]

A problem of Chvátal [Ch74], who proved it when we replace the closed under subsets condition with the (stronger) condition that, assuming all sets in $\mathcal{F}$ are subsets of $\{1,\ldots,n\}$, whenever $A\in \mathcal{F}$ and there is an injection $f:B\to A$ such that $x\leq f(x)$ for all $x\in B$ then $B\in \mathcal{F}$.

Sterboul [St74] proved this when, letting $\mathcal{G}$ be the maximal sets (under inclusion) in $\mathcal{F}$, all sets in $\mathcal{G}$ have the same size, $\lvert A\cap B\rvert\leq 1$ for all $A\neq B\in \mathcal{G}$, and at least two sets in $\mathcal{G}$ have non-empty intersection.

Frankl and Kupavskii [FrKu23] have proved this when $\mathcal{F}$ has covering number $2$.

Borg [Bo11] has proposed a weighted generalisation of this conjecture, which he proves under certain additional assumptions.

SOLVED

Let $k\geq 4$. If $\mathcal{F}$ is a family of subsets of $\{1,\ldots,n\}$ with $\lvert A\rvert=k$ for all $A\in \mathcal{F}$ and $\lvert \mathcal{F}\rvert >\binom{n-2}{k-2}$ then there are $A,B\in\mathcal{F}$ such that $\lvert A\cap B\rvert=1$.

SOLVED - $250

Let $r\geq 1$ and define $T(n,r)$ to be maximal such that there exists a family $\mathcal{F}$ of subsets of $\{1,\ldots,n\}$ of size $T(n,r)$ such that $\lvert A\cap B\rvert\neq r$ for all $A,B\in \mathcal{F}$.

Estimate $T(n,r)$ for $r\geq 2$. In particular, is it true that for every $\epsilon>0$ there exists $\delta>0$ such that for all $\epsilon n<r<(1/2-\epsilon) n$ we have \[T(n,r)<(2-\delta)^n?\]

It is trivial that $T(n,0)=2^{n-1}$. Frankl and Füredi [FrFu84] proved that, for fixed $r$ and $n$ sufficiently large in terms of $r$, the maximal $T(n,r)$ is achieved by taking
\[\mathcal{F} = \left\{ A\subseteq \{1,\ldots,n\} : \lvert A\rvert> \frac{n+r}{2}\textrm{ or }\lvert A\rvert < r\right\}\]
when $n+r$ is odd, and
\[\mathcal{F} = \left\{ A\subseteq \{1,\ldots,n\} : \lvert A\backslash \{1\}\rvert\geq \frac{n+r}{2}\textrm{ or }\lvert A\rvert < r\right\}\]
when $n+r$ is even. (Frankl [Fr77b] had earlier proved this for $r=1$ and all $n$.)

An affirmative answer to the second question implies that the chromatic number of the unit distance graph in $\mathbb{R}^n$ (with two points joined by an edge if the distance between them is $1$) grows exponentially in $n$, which was proved by alternative methods by Frankl and Wilson [FrWi81] - see [704].

The answer to the second question is yes, proved by Frankl and Rödl [FrRo87].

See also [702].

OPEN

Let $G_n$ be the unit distance graph in $\mathbb{R}^n$, with two vertices joined by an edge if and only if the distance between them is $1$.

Estimate the chromatic number $\chi(G_n)$. Does it grow exponentially in $n$? Does \[\lim_{n\to \infty}\chi(G_n)^{1/n}\] exist?

A generalisation of the Hadwiger-Nelson problem (which addresses $n=2$). Frankl and Wilson [FrWi81] proved exponential growth:
\[\chi(G_n) \geq (1+o(1))1.2^n.\]
The trivial colouring (by tiling with cubes) gives
\[\chi(G_n) \leq (2+\sqrt{n})^n.\]
Larman and Rogers [LaRo72] improved this to
\[\chi(G_n) \leq (3+o(1))^n,\]
and conjecture the truth may be $(2^{3/2}+o(1))^n$. Prosanov [Pr20] has given an alternative proof of this upper bound.

OPEN

Let $G$ be a finite unit distance graph in $\mathbb{R}^2$ (i.e. the vertices are a finite collection of points in $\mathbb{R}^2$ and there is an edge between two points f and only if the distance between them is $1$).

Is there some $k$ such that if $G$ has girth $\geq k$ (i.e. $G$ contains no cycles of length $<k$) then $\chi(G)\leq 3$?

The maximal value of $\chi(G)$ (without a girth condition) is the Hadwiger-Nelson problem. There are unit distance graphs (e.g. the Moser spindle) with $\chi(G)=4$ of girth $3$. de Grey [dG18] has constructed a unit distance graph $G$ with $\chi(G)=5$. (I do not know what the largest girth achieved is by these recent constructions.)

Wormald [Wo79] has constructed a unit distance graph with $\chi(G)=4$ and girth $5$, with $6448$ vertices. O'Donnell [OD94] has constructed a unit distance graph with $\chi(G)=4$ and girth $4$, with $56$ vertices. Chilakamarri [Ch95] has constructed an infinite family of unit distance graphs with $\chi(G)=4$ and girth $4$, the smallest of which has $47$ vertices.

OPEN

Let $L(r)$ be such that if $G$ is a graph formed by taking a finite set of points $P$ in $\mathbb{R}^2$ and some set $A\subset (0,\infty)$ of size $r$, where the vertex set is $P$ and there is an edge between two points if and only if their distance is a member of $A$, then $\chi(G)\leq L(r)$.

Estimate $L(r)$. In particular, is it true that $L(r)\leq r^{O(1)}$?

The case $r=1$ is the Hadwiger-Nelson problem, for which it is known that $5\leq L(1)\leq 7$.

OPEN - $500

Let $A\subset \mathbb{N}$ be a finite Sidon set. Is there some set $B$ with $A\subseteq B$ which is perfect difference set modulo $p^2+p+1$ for some prime $p$?

OPEN - $500

Determine, for any $k>r>2$, the value of
\[\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},\]
where $\mathrm{ex}_r(n,K_k^r)$ is the largest number of $r$-edges which can placed on $n$ vertices so that there exists no $K_k^r$, a set of $k$ vertices which is covered by all $\binom{k}{r}$ possible $r$-edges.

Turán proved that, when $r=2$, this limit is
\[\frac{1}{2}\left(1-\frac{1}{k-1}\right).\]
Erdős [Er81] offered \$500 for the determination of this value for any fixed $k>r>2$, and \$1000 for 'clearing up the whole set of problems'.

See also [500] for the case $r=3$ and $k=4$.

OPEN - $500

Is it true that, for every bipartite graph $G$, there exists some $\alpha\in [0,1)$ such that
\[\lim_{n\to \infty}\frac{\mathrm{ex}(n;G)}{n^{1+\alpha}}\]
exists and is in $(0,\infty)$?

A problem of Erdős and Simonovits. This is not true for hypergraphs, as shown by Ruzsa and Szemerédi [RuSz78], who proved that if $G$ is a $3$-uniform hypergraph on $6$ vertices containing $3$ $3$-edges then $\mathrm{ex}_3(n;G)=o(n^2)$ and yet for every $\epsilon >0$
\[\mathrm{ex}_3(n;G) >n^{2-\epsilon}\]
for all large enough $n$.

See also [571].

OPEN

Does every regular graph of degree $4$ contain a regular subgraph of degree $3$? Is there any $r$ such that every regular graph of degree $r$ must contain a regular subgraph of degree $3$?

A problem of Berge (or Berge and Sauer). Alon, Friedland, and Kalai [AFK84] proved that every $4$-regular graph plus an edge contains a $3$-regular subgraph, and hence in particular every $r$-regular graph with $r\geq 5$ contains a $3$-regular subgraph.

SOLVED

Let $G$ be a $3$-uniform hypergraph with $6$ vertices and $3$ $3$-edges. Is it true that
\[\mathrm{ex}_3(n,G)=o(n^2)?\]

A conjecture of Brown, Erdős, and Sós. The answer is yes, proved by Ruzsa and Szemerédi [RuSz78] (this is known as the Ruzsa-Szemerédi problem).

In [Er81] Erdős asks whether the same is true for any $3$-uniform hypergraph on $k$ vertices with $k-3$ $3$-edges.

SOLVED

Let $G$ be a graph on $n$ vertices with chromatic number $\chi(G)$ and let $\sigma(G)$ be the maximal $k$ such that $G$ contains a subdivision of $K_k$. Is it true that
\[\chi(G) \ll \frac{n^{1/2}}{\log n}\sigma(G)?\]

Hajós originally conjectured that $\chi(G)\leq \sigma(G)$, which was proved by Dirac [Di52] when $\chi(G)=4$. Catlin [Ca74] disproved Hajós' conjecture for all $\chi(G)\geq 7$, and Erdős and Fajtlowicz [ErFa81] disproved it in a strong form, showing that in fact for almost all graphs on $n$ vertices,
\[\chi(G) \gg \frac{n^{1/2}}{\log n}\sigma(G).\]

The answer is yes, proved by Fox, Lee, and Sudakov [FLS13].

SOLVED

Is there some constant $C>0$ such that any graph on $n$ vertices with $\geq Cr^2n$ edges contains a subdivision of $K_r$?

A conjecture of Erdős, Hajnal, and Mader. Dirac [Di60] proved that every graph on $n$ vertices with at least $2n-2$ edges contains a subdivision of $K_4$, and conjectured that $3n-5$ edges forces a subdivision of $K_5$.

Mader [Ma67] proved that $\geq 2^{\binom{r}{2}}n$ edges suffices.

The answer is yes, proved independently by Komlós and Szemerédi [KoSz96] and Bollobás and Thomason [BoTh96].

OPEN

Let $\mathrm{ex}_r(n;K_{r+1}^r)$ be the maximum number of $r$-edges that can be placed on $n$ vertices without forming a $K_{r+1}^r$ (the $r$-uniform complete graph on $r+1$ vertices).

Is every $r$-hypergraph $G$ on $n$ vertices the union of at most $\mathrm{ex}_{r}(n;K_{r+1}^r)$ many copies of $K_r^r$ and $K_{r+1}^r$, no two of which share a $K_r^r$?

A conjecture of Erdős and Sauer.

SOLVED - $100

Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-colouring of the edges of $H$ there is a monochromatic copy of $G$.

Is it true that, if $P_n$ is the path of length $n$, then \[\hat{R}(P_n)/n\to \infty\] and \[\hat{R}(P_n)/n^2 \to 0?\]

A problem of Erdős, Faudree, Rousseau, and Schelp.

Answered by Beck [Be83b], who proved that in fact $\hat{R}(P_n)\ll n$.

SOLVED

Let $W(3,k)$ be the van der Waerden number defined as the minimum $n$ such that in any red/blue colouring of $\{1,\ldots,n\}$ there exists either a red $3$-term arithmetic progression or a blue $k$-term arithmetic progression.

Give reasonable bounds for $W(3,k)$. In particular, give any non-trivial lower bounds for $W(3,k)$ and prove that $W(3,k) < \exp(k^c)$ for some constant $c<1$.

While we do not have a full understanding of the growth of $W(3,k)$, both of the specific challenges of Erdős have been met.

Green [Gr22] established the superpolynomial lower bound \[W(3,k) \geq \exp\left( c\frac{(\log k)^{4/3}}{(\log\log k) ^{1/3}}\right)\] for some constant $c>0$ (in particular disproving a conjecture of Graham that $W(3,k)\ll k^2$). Hunter [Hu22] improved this to \[W(3,k) \geq \exp\left( c\frac{(\log k)^{2}}{\log\log k}\right).\] The first to show that $W(3,k) < \exp(k^c)$ for some $c<1$ was Schoen [Sc21]. The best upper bound currently known is \[W(3,k) \ll \exp\left( O((\log k)^9)\right),\] which follows from the best bounds known for sets without three-term arithmetic progressions (see [BlSi23] which improves slightly on the bounds due to Kelley and Meka [KeMe23]).

SOLVED

Let $k>r$ and $n$ be sufficiently large in terms of $k$ and $r$. Does there always exist a block $r-(n,k,1)$ design (or Steiner system with parameters $(n,k,r)$), provided the trivial necessary divisibility conditions $\binom{k-i}{r-i}\mid \binom{n-i}{r-i}$ are satisfied for every $0\leq i<r$?

That is, can one find a family of $\binom{n}{k}\binom{k}{r}^{-1}$ many subsets of $\{1,\ldots,n\}$, all of size $k$, such that any $A\subseteq \{1,\ldots,n\}$ of size $r$ is contained in exactly one set in the family?

OPEN

If there is a finite projective plane of order $n$ then must $n$ be a prime power?

A finite projective plane of order $n$ is a collection of subsets of $\{1,\ldots,n^2+n+1\}$ of size $n+1$ such that every pair of elements is contained in exactly one set.

These always exist if $n$ is a prime power. This conjecture has been proved for $n\leq 11$, but it is open whether there exists a projective plane of order $12$.

Bruck and Ryser [BrRy49] have proved that if $n\equiv 1\pmod{4}$ or $n\equiv 2\pmod{4}$ then $n$ must be the sum of two squares. For example, this rules out $n=6$ or $n=14$. The case $n=10$ was ruled out by computer search [La97].

OPEN

Let $f(n)$ be the maximum number of mutually orthogonal Latin squares of order $n$. Is it true that
\[f(n) \gg n^{1/2}?\]

Euler conjectured that $f(n)=1$ when $n\equiv 2\pmod{4}$, but this was disproved by Bose, Parker, and Shrikhande [BPS60] who proved $f(n)\geq 2$ for $n\geq 7$.

Chowla, Erdős, and Straus [CES60] proved $f(n) \gg n^{1/91}$. Wilson [Wi74] proved $f(n) \gg n^{1/17}$. Beth [Be83c] proved $f(n) \gg n^{1/14.8}$.

OPEN

Call a sequence $1< X_1\leq \cdots \leq X_m\leq n$ block-compatible if there is a pairwise balanced block design $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ such that $\lvert A_i\rvert=X_i$ for $1\leq i\leq m$. (A pairwise block design means that every pair in $\{1,\ldots,n\}$ is contained in exactly one of the $A_i$.)

Are there necessary and sufficient conditions for $(X_i)$ to be block-compatible?

Is there some constant $c>0$ such that for all large $n$ there are \[\geq \exp(c n^{1/2}\log n)\] many block-compatible sequences for $\{1,\ldots,n\}$?

Erdős noted that a trivial necessary condition is $\sum_i \binom{X_i}{2}=\binom{n}{2}$, but wasn't sure if there would be a reasonable necessary and sufficient condition.

He could prove that there are \[\leq \exp(O(n^{1/2}\log n))\] many block-compatible sequences for $\{1,\ldots,n\}$.

See also [733].

OPEN

Call a sequence $1<X_1\leq\cdots X_m\leq n$ line-compatible if there is a set of $n$ points in $\mathbb{R}^2$ such that there are $m$ lines $\ell_1,\ldots,\ell_m$ containing at least two points, and the number of points on $\ell_i$ is exactly $X_i$.

Prove that there are at most \[\exp(O(n^{1/2}))\] many line-compatible sequences.

Erdős writes that it is 'easy' to prove there are at least
\[\exp(cn^{1/2})\]
many such sequences for some constant $c>0$, but expects proving the upper bound to be difficult. Once it is done, he asks for the existence and value of
\[\lim_{n\to \infty}\frac{\log f(n)}{n^{1/2}},\]
where $f(n)$ counts the number of line-compatible sequences.

See also [732].

OPEN

Find, for all large $n$, a pairwise balanced block design $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ such that, for all $t$, there are $O(n^{1/2})$ many $i$ such that $\lvert A_i\rvert=t$.

$A_1,\ldots,A_m$ is a pairwise balanced block design if every pair in $\{1,\ldots,n\}$ is contained in exactly one of the $A_i$.

Erdős [Er81] writes 'this will be probably not be very difficult to prove but so far I was not successful'.

Erdős and de Bruijn proved that if $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ is a pairwise balanced block design then $m\geq n$, and this implies there must be some $t$ such that there are $\gg n^{1/2}$ many $t$ with $\lvert A_i\rvert=t$.

SOLVED

Given any $n$ points in $\mathbb{R}^2$ when can one give positive weights to the points such that the sum of the weights of the points along every line containing at least two points is the same?

A problem of Murty, who conjectured this is only possible in one of four cases: all points on a line, no three points on a line, $n-1$ on a line, and a triangle, the angle bisectors, and the incentre (or a projective equivalence).

The previous configurations are the only examples, as proved by Ackerman, Buchin, Knauer, Pinchasi, and Rote [ABKPR08].

OPEN

Let $G$ be a graph with chromatic number $\aleph_1$. Is there, for any integer $m\geq 1$, some graph $G_m$ of chromatic number $m$ such that every finite subgraph of $G_m$ is a subgraph of $G$?

A conjecture of Walter Taylor.

More generally, Erdős asks to characterise families $\mathcal{F}_\alpha$ of finite graphs such that there is a graph of chromatic number $\aleph_\alpha$ all of whose finite subgraphs are in $\mathcal{F}_\alpha$.

OPEN

Let $G$ be a graph with chromatic number $\aleph_1$. Must there exist an edge $e$ such that, for all large $n$, $G$ contains a cycle of length $n$ containing $e$?

OPEN

Let $\mathfrak{m}$ be an infinite cardinal and $G$ be a graph with chromatic number $\mathfrak{m}$. Is it true that, for every infinite cardinal $\mathfrak{n}< \mathfrak{m}$, there exists a subgraph of $G$ with chromatic number $\mathfrak{n}$?

A question of Galvin, who proved that the answer is no if we ask for the subgraph to be induced (assuming $\aleph_1 < 2^{\aleph_0}$).

OPEN

Let $\mathfrak{m}$ be an infinite cardinal and $G$ be a graph with chromatic number $\mathfrak{m}$. Let $C\geq 1$. Must $G$ contain a subgraph of chromatic number $\mathfrak{m}$ which does not contain any odd cycle of length $\leq C$?

A question of Erdős and Hajnal. Rödl proved this is true if $\mathfrak{m}=\aleph_0$ and $C=3$.

In [Er81] Erdős also asks the same question but with girth (i.e. the subgraph does not contain any cycle at all of length $\leq C$).

OPEN

Let $T_2,\ldots,T_n$ be a collection of trees such that $T_k$ has $k$ vertices. Can we always write $K_n$ as the edge disjoint union of the $T_k$?

A conjecture of Gyárfás, known as the tree packing conjecture.

Gyárfás and Lehel [GyLe78] proved that this holds if all but at most $2$ of the trees are stars, or if all the trees are stars or paths. Fishburn [Fi83] proved this for $n\leq 9$. Bollobás [Bo83] proved that the smallest $\lfloor n/\sqrt{2}\rfloor$ many trees can always be packed greedily into $K_n$.

Joos, Kim, Kühn, and Osthus [JKKO19] proved that this conjecture holds when the trees have bounded maximum degree. Allen, Böttcher, Clemens, Hladky, Piguet, and Taraz [ABCHPT21] proved that this conjecture holds when all the trees have maximum degree $\leq c\frac{n}{\log n}$ for some constant $c>0$.

Janzer and Montgomery [JaMo24] have proved that there exists some $c>0$ such that the largest $cn$ trees can be packed into $K_n$.

OPEN

Let $k$ be a large fixed constant. Let $f_k(n)$ be the minimal $m$ such that there exists a graph $G$ on $n$ vertices with chromatic number $k$, such that every proper subgraph has chromatic number $<k$, and $G$ can be made bipartite by deleting $m$ edges.

Is it true that $f_k(n)\to \infty$ as $n\to \infty$? In particular, is it true that $f_4(n) \gg \log n$?

A problem of Erdős, Hajnal, and Szemerédi [EHS82]. Odd cycles show that $f_3(n)=1$, but they expect $f_4(n)\to \infty$. Gallai [Ga68] gave a construction which shows
\[f_4(n) \ll n^{1/2},\]
and Lovász extended this to show
\[f_k(n) \ll n^{1-\frac{1}{k-2}}.\]
It is possible that these are the true orders of magnitude.

SOLVED

Describe the size of the second largest component of the random graph on $n$ vertices, where each edge is included independently with probability $1/n$.

Erdős believed that almost surely the second largest component has size $\ll \log n$. This is true, as proved by Komlós, Sulyok, and Szemerédi [KSS80].

SOLVED

Is it true that, almost surely, a random graph on $n$ vertices with $\geq (\tfrac{1}{2}+\epsilon)n\log n$ edges is Hamiltonian?

A conjecture of Erdős and Rényi [ErRe66], who proved that almost surely such a graph has a perfect matching (when $n$ is even).

This is true. Pósa [Po76] proved that almost surely a random graph with $\geq Cn\log n$ edges is Hamiltonian for some large constant $C$, and Komlós and Szemerédi [KoSz83] proved that \[\geq \frac{1}{2}n\log n+\frac{1}{2}n\log\log n+w(n)n\] edges suffices, for any function $w$ which $\to \infty$ as $n\to \infty$.

SOLVED

How large should $\ell(n)$ be such that, almost surely, a random $3$-uniform hypergraph on $3n$ vertices with $\ell(n)$ edges must contain $n$ vertex-disjoint edges?

Asked to Erdős by Shamir in 1979. This is often known as Shamir's problem. Erdős writes: 'Many of the problems on random hypergraphs can be settled by the same methods as used for ordinary graphs and usually one can guess the answer almost immediately. Here we have no idea of the answer.'

This is now essentially completely understood: Johansson, Kahn, and Vu [JKV08] proved that the threshold is $\ell(n)\asymp n\log n$. The precise asymptotic was given by Kahn [Ka23], proving that the threshold is $\sim n\log n$ (also for the general problem over $r$-uniform hypergraphs).