Erdős called this 'perhaps my first serious problem' (in [Er98] he dates it to 1931). 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}}.\] (In [Er85c] Erdős offered \$100 for any improvement of the constant $1/4$ here.)

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

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.

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

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

The trivial greedy construction achieves $\gg N^{1/3}$. The first improvement on this was achieved by Ajtai, Komlós, and Szemerédi [AKS81b], who found an infinite Sidon set with growth rate $\gg (N\log 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.\] 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$.

It is possible that this is true even with $g(N)=O(1)$, from which the Erdős-Turán conjecture [28] would follow.

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

A suitably constructed random set has this property if we are allowed to ignore an exceptional set of density zero. The challenge is obtaining this with no exceptional set. Erdős believed the answer should be no. Erdős and Sárkzözy proved that \[\frac{\lvert 1_A\ast 1_A(n)-\log n\rvert}{\sqrt{\log n}}\to 0\] is impossible. Erdős suggests it may even be true that the $\liminf$ and $\limsup$ of $1_A\ast 1_A(n)/\log n$ are always separated by some absolute constant.

The Erdős discrepancy problem. This is true, and was proved by Tao [Ta16], who also proved the more general case when $f$ takes values on the unit sphere.

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.

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

Conjectured by Erdős, Ko, and Rado [ErKoRa61]. This inequality would be best possible, as shown by taking $\mathcal{F}$ to be the collection of all subsets of $[4n]$ of size $2n$ containing at least $n+1$ elements from $[2n]$.

Proved by Ahlswede and Khachatrian [AhKh97], who more generally showed the following. Let $2\leq t\leq k\leq m$ and let $r\geq 0$ be such that \[\frac{1}{r+1}\leq \frac{m-2k+2t-2}{(t-1)(k-t+1)}< \frac{1}{r}.\] The largest possible family of subsets of $[m]$ of size $k$, such that the pairwise intersections have size at least $t$, is the family of all subsets of $[m]$ of size $k$ which contain at least $t+r$ elements from $\{1,\ldots,t+2r\}$.

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

The unit distance problem. In [Er94b] Erdős dates this conjecture to 1946. In [Er82e] he offers \$300 for the upper bound $n^{1+o(1)}$.

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.

See also [92], [96], and [605].

This is a stronger form of the unit distance conjecture (see [90]).

The set of lattice points imply $f(n) > n^{c/\log\log n}$ for some constant $c>0$. Erdős offered \$500 for a proof that $f(n) \leq n^{o(1)}$ but only \$100 for a counterexample.

It is trivial that $f(n) \ll n^{1/2}$. A result of Pach and Sharir implies $f(n) \ll n^{2/5}$.

Fishburn (personal communication to Erdős) proved that $6$ is the smallest $n$ such that $f(n)=3$ and $8$ is the smallest $n$ such that $f(n)=4$, and suggested that the lattice points may not be best example.

See also [754].

The case when the points determine a convex polygon was been solved by Fishburn [Al63]. Note it is trivial that $\sum f(u_i)=\binom{n}{2}$. Solved by Guth and Katz [GuKa15] who proved the upper bound \[ \sum_i f(u_i)^2 \ll n^3\log n.\]

See also [94].

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.

See also [216], [651], and [838].

Conjectured by Erdős and Simonovits [ErSi84]. Erdős first offered \$250 for a proof and \$100 for a counterexample, but in [Er93] offered \$500 for a counterexample.

Disproved by Janzer [Ja21] who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that \[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]

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

Proved by Kelley and Meka [KeMe23]. In [ErGr80] and [Er81] it is conjectured that this holds for every $k$-term arithmetic progression.

See also [3].

Note that if $A$ is a set of integers then the condition implies that $A$ is a primitive set (that is, no element of $A$ is divisible by any other), for which the convergence of $\sum_{n\in A}\frac{1}{n\log n}$ was proved by Erdős [Er35], and the upper bound \[\sum_{n<x}\frac{1}{n}\ll \frac{\log x}{\sqrt{\log\log x}}\] was proved by Behrend [Be35]. This $O(\cdot)$ bound was improved to a $o(\cdot)$ bound by Erdős, Sárkőzy, and Szemerédi [ESS67].

In [Er73] mentions an unpublished proof of Haight that \[\lim \frac{\lvert A\cap [1,x]\rvert}{x}=0\] holds if the elements of $A$ are independent over $\mathbb{Q}$.

Over the years Erdős asked for various different quantitative estimates, for example \[\liminf \frac{\lvert A\cap [1,x]\rvert}{x}=0\] or even (motivated by Behrend's bound) \[\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}\ll \frac{\log x}{\sqrt{\log\log x}}.\] In [Er97c] he offers \$500 for resolving the questions in the main problem statement above.

This was partially resolved by Koukoulopoulos, Lamzouri, and Lichtman [KLL25], who proved that we must have \[\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}=o(\log n).\]

See also [858].

Conjectured by Erdős and Simonovits [ErSi84]. Open even for $r=2$. Alon, Krivelevich, and Sudakov [AKS03] have proved \[\mathrm{ex}(n;H) \ll n^{2-1/4r}.\] They also prove the full Erdős-Simonovits conjectured bound if $H$ is bipartite and the maximum degree in one component is $r$.

See also [113] and [147].

See also the entry in the graphs problem collection.

Conjectured by Erdős and Simonovits [ErSi84]. Disproved by Janzer [Ja21], who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that \[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]

See also [113], [146], and [714].

See also the entry in the graphs problem collection.

For $\alpha=0$ this is the usual Ramsey function. A conjecture of Erdős, Hajnal, and Rado (see [562]) implies that \[ F^{(t)}(n,0)\asymp \log_{t-1} n\] and results of Erdős and Spencer imply that \[F^{(t)}(n,\alpha) \gg_\alpha (\log n)^{\frac{1}{t-1}}\] for all $\alpha>0$, and a similar upper bound holds for $\alpha$ close to $1/2$.

Erdős believed there might be just one jump, occcurring at $\alpha=0$.

Conlon, Fox, and Sudakov [CFS11] have proved that, for any fixed $\alpha>0$, \[F^{(3)}(n,\alpha) \ll_\alpha \sqrt{\log n}.\] Coupled with the lower bound above, this implies that there is only one jump for fixed $\alpha$ when $t=3$, at $\alpha=0$.

For all $\alpha>0$ it is known that \[F^{(t)}(n,\alpha)\gg_t (\log n)^{c_\alpha}.\] See also [563].

See also the entry in the graphs problem collection.

The answer is yes, as proved by Montgomery and Vaughan [MoVa86], who in fact proved that for any $\gamma\geq 1$ \[ \sum_{1\leq k<\phi(n)}(a_{k+1}-a_k)^\gamma \ll \frac{n^\gamma}{\phi(n)^{\gamma-1}}.\] This general form was also asked by Erdős in [Er73].

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.

A special case of [562]. A problem of Erdős, Hajnal, and Rado [EHR65], who prove the bounds \[2^{cn^2}< R_3(n)< 2^{2^{n}}\] for some constant $c>0$.

Erdős, Hajnal, Máté, and Rado [EHMR84] have proved a doubly exponential lower bound for the corresponding problem with $4$ colours.

See also the entry in the graphs problem collection.

Similar problems were investigated by Erdős, Galvin, and Hajnal [EGH75]. Erdős claims that for graphs the problem is completely solved: a graph of chromatic number $\geq \aleph_1$ must contain all finite bipartite graphs but need not contain any fixed odd cycle.

A problem of Erdős, Hajnal, and Milner [EHM70], who proved this is true for $\alpha < \omega_1^{\omega+2}$.

In [Er82e] Erdős offers \$250 for showing what happens when $\alpha=\omega_1^{\omega+2}$ and \$500 for settling the general case.

Larson [La90] proved this is true for all $\alpha<2^{\aleph_0}$ assuming Martin's axiom.

The pinned distance problem, a stronger form of [89]. The example of an integer grid show that $n/\sqrt{\log n}$ would be best possible.

It may be true that there are $\gg n$ many such points, or that this is true on average. In [Er97e] Erdős offers \$500 for a solution to this problem, but it is unclear whether he intended this for proving the existence of a single such point or for $\gg n$ many such points.

In [Er97e] Erdős wrote that he initially 'overconjectured' and thought that the answer to this problem is the same as for the number of distinct distances between all pairs (see [89]), but this was disproved by Harborth. It could be true that the answers are the same up to an additive factor of $n^{o(1)}$.

The best known bound is \[\gg n^{c-o(1)},\] due to Katz and Tardos [KaTa04], where \[c=\frac{48-14e}{55-16e}=0.864137\cdots.\]

See also [44] and [329].

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

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