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".
The sequence of minimal $N$ for a given $n$ is A276661 in the OEIS.
See also [350].
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] (see [219]).
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].
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.
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.\]
Is it true that \[f(n) \ll n?\]
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)$.
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].
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$.
See also the entry in the graphs problem collection.
See also [57].
In [Er81] it is further conjectured that \[\max_{md\leq x}\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert \gg \log x.\]
In [Er85c] Erdős also asks about the special case when $f$ is multiplicative.
A shorter and simpler proof of an upper bound of the strength $4-c$ for some constant $c>0$ (and a generalisation to the case of more than two colours) was given by Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba [BBCGHMST24].
This problem is #3 in Ramsey Theory in the graphs problem collection.
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].
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.
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.
In [Er79b] Erdős also asks whether \[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]
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$?
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].
See also [3].
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$.
This problem is #17 in Ramsey Theory in the graphs problem collection.
A construction due to Pyber, Rödl, and Szemerédi [PRS95] shows that this is best possible.
The best bound available is due to Bucić and Montgomery [BM22], who prove that $O(n\log^*n)$ many cycles and edges suffice, where $\log^*$ is the iterated logarithm function.
Conlon, Fox, and Sudakov [CFS14] proved that $O_\epsilon(n)$ cycles and edges suffice if $G$ has minimum degree at least $\epsilon n$, for any $\epsilon>0$.
See also [583].
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.\]
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$.
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]).
This problem is #2 in Ramsey Theory in the graphs problem collection.
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].
See also [712] for the general case.
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$.
Is there some constant $c>0$ such that \[R_3(n) \geq 2^{2^{cn}}?\]
A rational $\alpha\in [1,2]$ for which the first problem holds is known as a Turán exponent. Known Turán exponents are:
See also [713] and the entry in the graphs problem collection.
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.
This was proved by Aharoni and Berger [AhBe09].
Larson [La90] proved this is true for all $\alpha<2^{\aleph_0}$ assuming Martin's axiom.
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$?
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).
Alon has proved that the answer is no: if $q$ is a large prime power and $n=m=q^2+q+1$ then there exist $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ such that $\lvert A_i\rvert \geq \tfrac{2}{5}\sqrt{n}$ for all $i$ and $\lvert A_i\cap A_j\rvert\leq 1$ for all $i\neq j$, and yet if $B$ has non-empty intersection with all $A_i$ then there exists $A_j$ such that $\lvert B\cap A_j\rvert \gg \log n$. (The construction is to take random subsets of the lines of a projective plane.)
The weaker version that Erdős posed in [Er81] remains open, although Alon conjectures the answer there to also be no.
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.
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?\]
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].
Estimate the chromatic number $\chi(G_n)$. Does it grow exponentially in $n$? Does \[\lim_{n\to \infty}\chi(G_n)^{1/n}\] exist?
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$?
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.
Estimate $L(r)$. In particular, is it true that $L(r)\leq r^{O(1)}$?
See also [500] for the case $r=3$ and $k=4$.
See also [571].
The answer is yes, proved by Tashkinov [Ta82].
In [Er81] Erdős asks whether the same is true for any $3$-uniform hypergraph on $k$ vertices with $k-3$ $3$-edges.
The answer is yes, proved by Fox, Lee, and Sudakov [FLS13].
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].
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$?
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?\]
Answered by Beck [Be83b], who proved that in fact $\hat{R}(P_n)\ll n$.
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$.
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]).
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?
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.
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].
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}$.
The sequence of $f(n)$ is A001438 in the OEIS.
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\}$?
He could prove that there are \[\leq \exp(O(n^{1/2}\log n))\] many block-compatible sequences for $\{1,\ldots,n\}$.
Alon has proved there are at least \[2^{(\frac{1}{2}+o(1))n^{1/2}\log n}\]
many sequences which are block-compatible for $n$. See also [733].
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 expected proving the upper bound to be difficult. Once it is done, he asked 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.
This is true, and was proved by Szemerédi and Trotter [SzTr83].
See also [732].
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$.
The previous configurations are the only examples, as proved by Ackerman, Buchin, Knauer, Pinchasi, and Rote [ABKPR08].
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$.
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$).
This is true (for sufficiently large $n$) and was proved by Füredi [Fu92].
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$.
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$?
This conjecture was disproved by Rödl and Tuza [RoTu85], who proved that in fact $f_k(n)=\binom{k-1}{2}$ (for all sufficiently large $n$).
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$.
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).