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

Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15], building on work of Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], has shown (contrary to Erdős' expectations) that the answer is no: the smallest modulus must be at most $10^{18}$.

An alternative, simpler, proof was given by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22], who improved the bound on the smallest modulus to $616000$.

Asked by Erdős and Selfridge (sometimes also with Schinzel). They also asked whether there can be a covering system such that all the moduli are odd and squarefree. The answer to this stronger question is no, proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Hough and Nielsen [HoNi19] proved that at least one modulus must be divisible by either $2$ or $3$. A simpler proof of this fact was provided by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Selfridge has shown (as reported in [Sc67]) that such a covering system exists if a covering system exists with moduli $n_1,\ldots,n_k$ such that no $n_i$ divides any other $n_j$ (but the latter has been shown not to exist, see [586]).

Crocker [Cr71] has proved there are are $\gg\log\log N$ such integers in $\{1,\ldots,N\}$. Pan [Pa11] improved this to $\gg_\epsilon N^{1-\epsilon}$ for any $\epsilon>0$. Erdős believed this cannot be proved by covering systems, i.e. integers of the form $p+2^k+2^l$ exist in every infinite arithmetic progression.

The sequence of such numbers is A006286 in the OEIS.

See also [10], [11], and [16].

Erdős described this as 'probably unattackable'. In [ErGr80] Erdős and Graham suggest that no such $k$ exists. Gallagher [Ga75] has shown that for any $\epsilon>0$ there exists $k(\epsilon)$ such that the set of integers which are the sum of a prime and at most $k(\epsilon)$ many powers of 2 has lower density at least $1-\epsilon$.

Granville and Soundararajan [GrSo98] have conjectured that at most $3$ powers of 2 suffice for all odd integers, and hence at most $4$ powers of $2$ suffice for all even integers. (The restriction to odd integers is important here - for example, Bogdan Grechuk has observed that $1117175146$ is not the sum of a prime and at most $3$ powers of $2$, and pointed out that parity considerations, coupled with the fact that there are many integers not the sum of a prime and $2$ powers of $2$ (see [9]) suggest that there exist infinitely many even integers which are not the sum of a prime and at most $3$ powers of $2$).

See also [9], [11], and [16].

Erdős called this conjecture 'rather silly'. Using covering congruences Erdős [Er50] proved that the set of such odd integers contains an infinite arithmetic progression.

Chen [Ch23] has proved the answer is no.

See also [9], [10], and [11].

The first prime without this property is $97$. The sequence of such primes is A038133 in the OEIS. These are called cluster primes.

Blecksmith, Erdős, and Selfridge [BES99] proved that the number of such primes is \[\ll_A \frac{x}{(\log x)^A}\] for every $A>0$, and Elsholtz [El03] improved this to \[\ll x\exp(-c(\log\log x)^2)\] for every $c<1/8$.

It is easy to see that almost all numbers are not practical. Erdős originally showed that $h(n!) <n$. Vose [Vo85] proved the existence of infinitely many practical $m$ such that $h(m)\ll (\log m)^{1/2}$.

The sequence of practical numbers is A005153 in the OEIS.

See also [304] and [825].

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.

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

Asked by Erdős and Tenenbaum. Ruzsa gave the following simple counterexample: let $A=\{n_1<n_2<\cdots \}$ where $n_l \equiv -(k-1)\pmod{p_k}$ for all $k\leq l$, where $p_k$ denotes the $k$th prime.

Tenenbaum asked the weaker variant (still open) where for every $\epsilon>0$ there is some $k=k(\epsilon)$ such that at least $1-\epsilon$ density of all integers have a divisor of the form $a+k$ for some $a\in A$.

By a simple averaging argument the set of moduli $[m_1,m_2]\cap \mathbb{N}$ has a choice of residue classes which form an $\epsilon(m_1,m_2)$-almost covering system with \[\epsilon(m_1,m_2)=\prod_{m_1\leq m\leq m_2}(1-1/m).\] A $0$-covering system is just a covering system, and so by Hough [Ho15] these only exist for $n_1<10^{18}$.

The answer is no, as proved by Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], who (among other results) prove that if \[1< C \leq N^{\frac{\log\log\log N}{4\log\log N}}\] then, for any $N\leq n_1<\cdots< n_k\leq CN$, the density of integers not covered for any fixed choice of residue classes is at least \[\prod_{i}(1-1/n_i)\] (and this density is achieved for some choice of residue classes as above).

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 existence of such a set was asked by Sidon to Erdős in 1932. Erdős (eventually) proved the existence of such a set using probabilistic methods. This problem asks for a constructive solution.

An explicit construction was given by Jain, Pham, Sawhney, and Zakharov [JPSZ24].

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] and [840].

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

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

See also [707].

This follows from the colouring result of Croot [Cr03]. Croot's result allows for $n_k \leq e^{C^k}$ for some constant $C>1$ (simply taking $n_k$ to be the lowest common multiple of some interval $[1,C^k]$). Sawhney has observed that there is also a doubly exponential lower bound, and hence this bound is essentially sharp.

Indeed, we must trivially have $\sum_{d|n_k}1/d \geq k$, or else there is a greedy colouring as a counterexample. Since $\prod_{p}(1+1/p^2)$ is finite we must have $\prod_{p|n_k}(1+1/p)\gg k$. To achieve the minimal $\prod_{p|n_k}p$ we take the product of primes up to $T$ where $\prod_{p\leq T}(1+1/p)\gg k$; by Mertens theorems this implies $T\geq C^{k}$ for some constant $C>1$, and hence $n_k\geq \prod_{p\mid n_k}p\geq \exp(cC^k)$ for some $c>0$.

The answer is yes, as proved by Croot [Cr03].

See also [298].

Solved by Bloom [Bl21], who showed that the quantitative threshold \[\sum_{n\in A}\frac{1}{n}\gg \frac{\log\log\log N}{\log\log N}\log N\] is sufficient. This was improved by Liu and Sawhney [LiSa24] to \[\sum_{n\in A}\frac{1}{n}\gg (\log N)^{4/5+o(1)}.\] Erdős speculated that perhaps even $\gg (\log\log N)^2$ might be sufficient. (A construction of Pomerance, as discussed in the appendix of [Bl21], shows that this would be best possible.)

See also [46] and [298].

This would follow immediately from the twin prime conjecture. The answer is yes, proved by Ford, Luca, and Pomerance [FLP10].

Erdős remarks that the last conjecture is probably easy, and that similar questions can be asked about $\sigma(n)$.

Solved by Tao [Ta23b], who proved that \[ \lvert A\rvert \leq \left(1+O\left(\frac{(\log\log x)^5}{\log x}\right)\right)\pi(x).\]

In [Er95c] Erdős further asks about the situation when $\phi(a_1)\leq \cdots \leq \phi(a_t)$.

Carmichael has asked whether there is an integer $t$ for which $\phi(n)=t$ has exactly one solution. Erdős has proved that if such a $t$ exists then there must be infinitely many such $t$.

See also [694].

The sum-product problem. Erdős and Szemerédi [ErSz83] proved a lower bound of $\lvert A\rvert^{1+c}$ for some constant $c>0$, and an upper bound of \[\lvert A\rvert^2 \exp\left(-c\frac{\log\lvert A\rvert}{\log\log \lvert A\rvert}\right)\] for some constant $c>0$. The lower bound has been improved a number of times. The current record is \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{1558}{1167}-o(1)}\] due to Rudnev and Stevens [RuSt22] (note $1558/1167=1.33504\cdots$).

There is likely nothing special about the integers in this question, and indeed Erdős and Szemerédi also ask a similar question about finite sets of real or complex numbers. The current best bound for sets of reals is the same bound of Rudnev and Stevens above. The best bound for complex numbers is \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{5}{4}},\] due to Solymosi [So05].

One can in general ask this question in any setting where addition and multiplication are defined (once one avoids any trivial obstructions such as zero divisors or finite subfields). For example, it makes sense for subsets of finite fields. The current record is that if $A\subseteq \mathbb{F}_p$ with $\lvert A\rvert <p^{5/8}$ then \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{11}{9}+o(1)},\] due to Rudnev, Shakan, and Shkredov [RSS20].

There is also a natural generalisation to higher-fold sum and product sets. For example, in [ErSz83] (and in [Er91]) Erdős and Szemerédi also conjecture that for any $m\geq 2$ and finite set of integers $A$ \[\max( \lvert mA\rvert,\lvert A^m\rvert)\gg \lvert A\rvert^{m-o(1)}.\] See [53] for more on this generalisation and [808] for a stronger form of the original conjecture. See also [818] for a special case.

The stated bounds are due to Burr and Erdős [BuEr85]. Resolved by Conlon, Fox, and Pham [CFP21], who constructed a Ramsey $2$-complete $A$ such that \[\lvert A\cap \{1,\ldots,N\}\rvert \ll (\log N)^2\] for all large $N$.

See also [55] and [843].

A paper of Burr and Erdős [BuEr85] proves both upper and lower bounds for $r=2$, showing that there exists some $c>0$ such that it cannot be true that \[\lvert A\cap \{1,\ldots,N\}\rvert \leq c(\log N)^2\] for all large $N$, and also constructing a Ramsey $2$-complete $A$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert \ll (\log N)^3.\] Burr has shown that the sequence of $k$th powers is Ramsey $r$-complete for every $r,k\geq 1$.

Solved by Conlon, Fox, and Pham [CFP21], who constructed for every $r\geq 2$ an $r$-Ramsey complete $A$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert \ll r(\log N)^2,\] and showed that this is best possible, in that there exists some constant $c>0$ such that if $A\subset \mathbb{N}$ satisfies \[\lvert A\cap \{1,\ldots,N\}\rvert \leq cr(\log N)^2\] for all large $N$ then $A$ cannot be $r$-Ramsey complete.

See also [54] and [843].

This was disproved for $k=212$ by Ahlswede and Khachatrian [AhKh94], who suggest that their methods can disprove this for arbitrarily large $k$.

Erdős later asked ([Er92b] and [Er95]) if the conjecture remains true provided $N\geq (1+o(1))p_k^2$ (or, in a weaker form, whether it is true for $N$ sufficiently large depending on $k$).

See also [534].

Conjectured by Erdős and Hajnal, and solved by Liu and Montgomery [LiMo20]. In [Er81] Erdős asks whether the $a_i$ must in fact have positive upper density. The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.

See also [65].

Conjectured by Mihók and Erdős. It is likely that $2^n$ can be replaced by any sufficiently quickly growing sequence (e.g. the squares).

David Penman has observed that this is certainly true if the graph has uncountable chromatic number, since by a result of Erdős and Hajnal [ErHa66] such a graph must contain arbitrarily large finite complete bipartite graphs (see also Theorem 3.17 of Reiher [Re24]).

Zach Hunter has observed that this follows from the work of Liu and Montgomery [LiMo20]: if $G$ has infinite chromatic number then, for infinitely many $r$, it must contain some finite connected subgraph $G_r$ with chromatic number $r$ (via the de Bruijn-Erdős theorem [dBEr51]). Each $G_r$ contains some subgraph $H_r$ with minimum degree at least $r-1$, and hence via Theorem 1.1 of [LiMo20] there exists some $\ell_r\geq r^{1-o(1)}$ such that $H_r$ contains a cycle of every even length in $[(\log \ell)^8,\ell]$.

See also [64].

Conjectured by Erdős and Gyárfás, who believed the answer must be negative, and in fact for every $r$ there must be a graph of minimum degree at least $r$ without a cycle of length $2^k$ for any $k\geq 2$.

This was solved in the affirmative if the minimum degree is larger than some absolute constant by Liu and Montgomery [LiMo20] (therefore disproving the above stronger conjecture of Erdős and Gyárfás). Liu and Montgomery prove a much stronger result: if the average degree of $G$ is sufficiently large then there is some large integer $\ell$ such that for every even integer $m\in [(\log \ell)^8,\ell]$, $G$ contains a cycle of length $m$.

An infinite tree with minimum degree $3$ shows that the answer is trivially false for infinite graphs.

See also the entry in the graphs problem collection.

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

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.

This has been proved by Bollobás [Bo77]. The best dependence of the constant $c(P)$ is unknown.

See also [72].

Bollobás [Bo77] proved that such a $c$ does exist if $A$ is an infinite arithmetic progression containing even numbers (see [71]).

Erdős was 'almost certain' that if $A$ is the set of powers of $2$ then no such $c$ exists (although he conjectured that $n$ vertices and average degree $\gg (\log n)^{C}$ suffices for some $C=O(1)$). If $A$ is the set of squares (or the set of $p\pm 1$ for $p$ prime) then he had no guess.

Solved by Verstraëte [Ve05], who gave a non-constructive proof that such a set $A$ exists.

Liu and Montgomery [LiMo20] proved that in fact this is true when $A$ is the set of powers of $2$ (more generally any set of even numbers which doesn't grow too quickly) - in particular this contradicts the previous belief of Erdős.

See also the entry in the graphs problem collection.

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.

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, Hajnal, and Szemerédi [EHS82].

See also [750].

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

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.

Erdős gave a simple probabilistic proof that $R(k) \gg k2^{k/2}$. Equivalently, this question asks for an explicit construction of a graph on $n$ vertices which does not contain any clique or independent set of size $\geq c\log n$ for some constant $c>0$. Cohen [Co15] (see the introduction for further history) constructed a graph on $n$ vertices which does not contain any clique or independent set of size \[\geq 2^{(\log\log n)^{C}}\] for some constant $C>0$. Li [Li23b] has recently improved this to \[\geq (\log n)^{C}\] for some constant $C>0$.

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

Asked by Erdős, Faudree, Rousseau, and Schelp [EFRS93]. $K_4$ is the only known example of such a graph.

Wigderson [Wi24] has proved that there are infinitely many such graphs (although his proof is not explicit, and an explicit example of such a graph apart from $K_4$ is still unknown.)

Asked by Erdős, Ordman, and Zalcstein [EOZ93], who proved an upper bound of $(1/4-\epsilon)n^2$ many cliques (for some very small $\epsilon>0$). The example of all edges between a complete graph on $n/3$ vertices and an empty graph on $2n/3$ vertices show that $n^2/6+O(n)$ is sometimes necessary.

A split graph is one where the vertices can be split into a clique and an independent set. Every split graph is chordal. Chen, Erdős, and Ordman [CEO94] have shown that any split graph can be partitioned into $\frac{3}{16}n^2+O(n)$ many cliques.

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

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

Conjectured by Erdős and Faudree, who showed that $2^{n/2}<f(n) \leq 2^{n-2}$. The first problem was solved by Verstraëte [Ve04], who proved \[f(n)\ll 2^{n-n^c}\] for some constant $c>0$.

One can also ask about the existence and value of $\lim f(n)^{1/n}$.

A weaker version of the conjecture asks for some constant $c$ such that $f(m)>f(n)-c$ for all $m>n$. This question can be asked for other graphs than $C_4$.

The best known result is due to Balogh, Hu, Lidicky, and Liu [BHLL14], who proved that $0.6068 n2^{n-1}$ edges suffice. Erdős [Er91] observes that there exist subgraphs with \[\geq \left(\frac{1}{2}+\frac{c}{n}\right)n2^{n-1}\] many edges without a $C_4$ (for some constant $c>0$). He suggests that it 'perhaps not hopeless' to determine the threshold exactly.

A similar question can be asked for other even cycles.

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

Erdős originally conjectured that $R(G)\geq R(k)$, which is trivial for $k=3$, but fails already for $k=4$, as Faudree and McKay [FaMc93] showed that $R(W)=17$ for the pentagonal wheel $W$.

Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 3/4$. Yuval Wigderson points out that $R(G)\gg 2^{k/2}$ for any $G$ with chromatic number $k$ (via a random colouring), which asymptotically matches the best-known lower bounds for $R(k)$.

This problem is #12 and #13 in Ramsey Theory in the graphs problem collection.

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.

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.

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

Solved by Altman [Al63]. The stronger variant that says there is one point which determines at least $\lfloor \frac{n+1}{2}\rfloor$ distinct distances is still open. Fishburn in fact conjectures that if $R(x)$ counts the number of distinct distances from $x$ then \[\sum_{x\in A}R(x) \geq \binom{n}{2}.\]

Szemerédi conjectured (see [Er97e]) that this stronger variant remains true if we only assume that no three points are on a line, and proved this with the weaker bound of $n/3$.

See also [660].

Solved by Fishburn [Al63]. Note it is trivial that $\sum f(u_i)=\binom{n}{2}$. The stronger conjecture that $\sum f(u_i)^2$ is maximal for the regular $n$-gon (for large enough $n$) is still open.

See also [95].

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

Erdős originally conjectured this with no $3$ vertices equidistant, but Danzer found a convex polygon on 9 points such that every vertex has three vertices equidistant from it (but this distance depends on the vertex), and Fishburn and Reeds [FiRe92] have found a convex polygon on 20 points such that every vertex has three vertices equidistant from it (and this distance is the same for all vertices).

If this fails for $4$, perhaps there is some constant for which it holds?

Erdős suggested this as an approach to solve [96]. Indeed, if this problem holds for $k+1$ vertices then, by induction, this implies an upper bound of $kn$ for [96].

The answer is no if we omit the requirement that the polygon is convex (I thank Boris Alexeev and Dustin Mixon for pointing this out), since for any $d$ there are graphs with minimum degree $d$ which can be embedded in the plane such that each edge has length one (for example one can take the $d$-dimensional hypercube graph on $2^d$ vertices). One can then connect the vertices in a cyclic order so that there are no self-intersections and no three consecutive vertices on a line, thus forming a (non-convex) polygon.

Thue proved that the minimal such diameter is achieved (asymptotically) by the points in a triangular lattice intersected with a circle. In general Erdős believed such a set must have very large intersection with the triangular lattice (perhaps as many as $(1-o(1))n$).

Erdős [Er94b] wrote 'I could not prove it but felt that it should not be hard. To my great surprise both B. H. Sendov and M. Simonovits doubted the truth of this conjecture.' In [Er94b] he offers \$100 for a counterexample but only \$50 for a proof.

The stated problem is false for $n=4$, for example taking the points to be vertices of a square. The behaviour of such sets for small $n$ is explored by Bezdek and Fodor [BeFo99].

See also [103].

Perhaps the diameter is even $\geq n-1$ for sufficiently large $n$. Piepmeyer has an example of $9$ such points with diameter $<5$. Kanold proved the diameter is $\geq n^{3/4}$. The bounds on the distinct distance problem [89] proved by Guth and Katz [GuKa15] imply a lower bound of $\gg n/\log n$.

There are examples of sets of $n$ points with $\sim n^2/6$ many collinear triples and no four points on a line. Such constructions are given by Burr, Grünbaum, and Sloane [BGS74] and Füredi and Palásti [FuPa84].

Grünbaum [Gr76] constructed an example with $\gg n^{3/2}$ such lines. Erdős speculated this may be the correct order of magnitude. This is false: Solymosi and Stojaković [SoSt13] have constructed a set with no five on a line and at least \[n^{2-O(1/\sqrt{\log n})}\] many lines containing exactly four points.

See also [102]. A generalisation of this problem is asked in [588].

A problem of Erdős and Purdy. It is not even known if $h_c(n)\geq 5$ (see [101]).

It is easy to see that $h_c(n) \ll_c n^{1/2}$, and Erdős originally suggested that perhaps a similar lower bound $h_c(n)\gg_c n^{1/2}$ holds. Zach Hunter has pointed out that this is false, even replacing $>3$ points on each line with $>k$ points: consider the set of points in $\{1,\ldots,m\}^d$ where $n\approx m^d$. These intersect any line in $\ll_d n^{1/d}$ points, and have $\gg_d n^2$ many pairs of points each of which determine a line with at least $k$ points. This is a construction in $\mathbb{R}^d$, but a random projection into $\mathbb{R}^2$ preserves the relevant properties.

This construction shows that $h_c(n) \ll n^{1/\log(1/c)}$.

In [Er81d] Erdős proved that $\gg n$ many circles is possible, and that there cannot be more than $n(n-1)$ many circles. Elekes [El84] has a simple construction of a set with $\gg n^{3/2}$ such circles. This may be the correct order of magnitude.

In [Er75h] Erdős also asks how many such unit circles there must be if the points are in general position.

See also [506] and [831].

Conjectured by Erdős and Purdy [ErPu95] (the prize is for a proof or disproof). A construction of Hickerson shows that this fails with $n-2$. A result independently proved by Beck [Be83] and Szemerédi and Trotter [SzTr83] (see [211]) implies it is true with $n-3$ replaced by $cn$ for some constant $c>0$.

In [Er94b] Erdős dates this conjecture to 'more than 60 years ago'.

It is trivial from the Cauchy-Schwarz inequality that $f(k^2)=4k$. Erdős also asks for which $n$ is it true that $f(n+1)=f(n)$.

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

In other words, is $G$ Ramsey size linear? A special case of [566]. In [Er95] Erdős specifically asks about the case $G=K_{3,3}$.

The graph $H_5$ can also be described as $K_4^*$, obtained from $K_4$ by subdividing one edge. ($K_4$ itself is not Ramsey size linear, since $R(4,n)\gg n^{3-o(1)}$, see [166].) Bradać, Gishboliner, and Sudakov [BGS23] have shown that every subdivision of $K_4$ on at least $6$ vertices is Ramsey size linear, and also that $R(H_5,H) \ll m$ whenever $H$ is a bipartite graph with $m$ edges and no isolated vertices.

See also the entry in the graphs problem collection.

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