Conjectured by Erdős and Turán [ErTu48]. Shockingly Erdős offered \$25000 for a disproof of this, but as he comments, it 'is certainly true'. (In [Er85c] he goes further and offers 'all the money I can earn, beg, borrow or steal for [a disproof]'.)

Indeed, the answer is yes, as proved by Banks, Freiberg, and Turnage-Butterbaugh [BFT15] with an application of the Maynard-Tao machinery concerning bounded gaps between primes [Ma15]. They in fact prove that, for any $m\geq 1$, there are infinitely many $n$ such that \[d_n<d_{n+1}<\cdots <d_{n+m}\] and infinitely many $n$ such that \[d_n> d_{n+1}>\cdots >d_{n+m}.\]

Asked by Erdős and Sárközy, who observed that $(2N/3,N]\cap \mathbb{N}$ is such a set. The answer is yes, as proved by Bedert [Be23].

For the infinite version see [12].

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

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

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

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

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.

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.

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.

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.

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

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

The weaker conjecture that $\limsup M_n=\infty$ was proved by Wagner, who show that there is some $c>0$ with $M_n>(\log n)^c$ infinitely often.

This was solved by Beck [Be91], who proved that there exists some $c>0$ such that \[\max_{n\leq N} M_n > N^c.\]

The Erdős similarity problem.

This is true if $A$ is unbounded or dense in some interval. It therefore suffices to prove this when $A=\{a_1>a_2>\cdots\}$ is a countable strictly monotone sequence which converges to $0$.

Steinhaus [St20] has proved this is false whenever $A$ is a finite set.

This conjecture is known in many special cases (but, for example, it is is open when $A=\{1,1/2,1/4,\ldots\}$. For an overview of progress we recommend a nice survey by Svetic [Sv00] on this problem.

Asked by Erdős and Pach. Hopf and Pannowitz [HoPa34] proved that the largest distance between points of $A$ can occur at most $n$ times, but it is unknown whether a second such distance must occur.

It may be true that there are at least $n^{1-o(1)}$ many such distances. In [Er97e] Erdős offers \$100 for 'any nontrivial result'.

See also [223] and [756].

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

Originally asked to Erdős by Bose. Bose and Chowla [BoCh62] provided a construction proving one half of this, namely \[(1+o(1))N^{1/3}\leq f(N).\] The best upper bound known to date is due to Green [Gr01], \[f(N) \leq ((7/2)^{1/3}+o(1))N^{1/3}\] (note that $(7/2)^{1/3}\approx 1.519\cdots$).

More generally, Bose and Chowla conjectured that the maximum size of $A\subseteq \{1,\ldots,N\}$ with all $r$-fold sums distinct (aside from the trivial coincidences) then \[\lvert A\rvert \sim N^{1/r}.\] This is known only for $r=2$ (see [30]).

A problem of Erdős and Entringer [EnEr72], who constructed a graph with \[\gg 2^{\binom{n}{2}-O(n^{3/2+o(1)})}\] many unique subgraphs. This was improved by Harary and Schwenk [HaSc73] and then by Brouwer [Br75], who constructed a graph with \[\gg \frac{2^{\binom{n}{2}-O(n)}}{n!}\] many unique subgraphs.

Note that there are $\sim 2^{\binom{n}{2}}/n!$ many non-isomorphic graphs on $n$ vertices (folklore, often attributed to Pólya), and hence the bound in the problem statement is trivially best possible.

Erdős believed Brouwer's construction was essentially best possible, but Spencer suggested that $\gg \frac{2^{\binom{n}{2}}}{n!}$ may be possible. Erdős offered \$100 for a construction and \$25 for a proof that no such construction is possible.

Erdős and Hajnal [ErHa67] first asked for the existence of any such graph. Existence was proved by Folkman [Fo70], but with very poor quantitative bounds. (As a result these quantities are often called Folkman numbers.) Let this particular Folkman number be denoted by $N$.

Frankl and Rödl [FrRo86] proved $N\leq 7\times 10^{11}$, which Spencer [Sp88] improved to $\leq 3\times 10^{9}$. This resolved the initial challenge of Erdős [Er75d] to beat $10^{10}$.

Lu [Lu07] proved $N\leq 9697$ vertices. The current record is due to Dudek and Rödl [DuRo08] who proved $N\leq 941$ vertices. For further information we refer to a paper of Radziszowski and Xu [RaXu07], who prove that $N\geq 19$ and speculate that $N\leq 127$.

See also the entry in the graphs problem collection.

A generalisation of [101] (which asks about $k=4$).

The restriction to $k\geq 4$ is necessary since Sylvester has shown that $f_3(n)= n^2/6+O(n)$. (See also Burr, Grünbaum, and Sloane [BGS74] and Füredi and Palásti [FuPa84] for constructions which show that $f_3(n)\geq(1/6+o(1))n^2$.)

For $k\geq 4$, Kárteszi [Ka] proved \[f_k(n)\gg_k n\log n.\] Grünbaum [Gr76] proved \[f_k(n) \gg_k n^{1+\frac{1}{k-2}}.\] Erdős speculated this may be the correct order of magnitude, but Solymosi and Stojaković [SoSt13] give a construction which shows \[f_k(n)\gg_k n^{2-O_k(1/\sqrt{\log n})}\]

A problem of Erdős and Surányi [ErSu59], who proved that $g(n) \geq (2-o(1))n$, and that $g(3)=4$. Their upper bound construction took $A$ as the set of $p_ip_j$ for $i\neq j$, where $p_1<\cdots <p_\ell$ is some set of primes such that $2p_1^2>p_\ell^2$.

Gallai was the first to consider problems of this type, and observed that $g(2)=2$ and $g(3)\geq 4$.

In [Er92c] Erdős offers '100 dollars or 1000 rupees', whichever is more, for a proof or disproof. (In 1992 1000 rupees was worth approximately \$38.60.)

Erdős and Surányi similarly asked what is the smallest $c_n\geq 1$ such that in any interval $I\subset [0,\infty)$ of length $c_n\max(A)$ there exists some $B\subseteq I\cap \mathbb{N}$ with $\lvert B\rvert=n$ such that \[\prod_{a\in A} a \mid \prod_{b\in B}b.\] They prove $c_2=1$ and $c_3=\sqrt{2}$, but have no good upper or lower bounds in general.

See also [709].

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

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