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

Suppose $A\subset \mathbb{R}^2$ has $\lvert A\rvert=n$ and minimises the number of distinct distances between points in $A$. Prove that for large $n$ there are at least two (and probably many) such $A$ which are non-similar.

For $n=5$ the regular pentagon is the unique such set (Erdős mysteriously remarks this was proved by 'a colleague').

OPEN - $500

Let $f(n)$ be maximal such that there exists a set $A$ of $n$ points in $\mathbb{R}^2$ in which every $x\in A$ has at least $f(n)$ points in $A$ equidistant from $x$.

Is it true that $f(n)\leq n^{o(1)}$? Or even $f(n) < n^{c/\log\log n}$ for some constant $c>0$?

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

If $n$ distinct points in $\mathbb{R}^2$ form a convex polygon then they determine at least $\lfloor \frac{n+1}{2}\rfloor$ distinct distances.

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

Suppose $n$ points in $\mathbb{R}^2$ determine a convex polygon and the set of distances between them is $\{u_1,\ldots,u_t\}$. Suppose $u_i$ appears as the distance between $f(u_i)$ many pairs of points. Then
\[\sum_i f(u_i)^2 \ll n^3.\]

SOLVED - $500

Let $x_1,\ldots,x_n\in\mathbb{R}^2$ determine the set of distances $\{u_1,\ldots,u_t\}$. Suppose $u_i$ appears as the distance between $f(u_i)$ many pairs of points. Then for all $\epsilon>0$
\[\sum_i f(u_i)^2 \ll_\epsilon n^{3+\epsilon}.\]

OPEN

If $n$ points in $\mathbb{R}^2$ form a convex polygon then there are $O(n)$ many pairs which are distance $1$ apart.

Conjectured by Erdős and Moser. Füredi [Fu90] proved an upper bound of $O(n\log n)$. A short proof of this bound was given by Brass and Pach [BrPa01]. The best known upper bound is
\[\leq n\log_2n+4n,\]
due to Aggarwal [Ag15].

Edelsbrunner and Hajnal [EdHa91] have constructed $n$ such points with $2n-7$ pairs distance $1$ apart. (This disproved an early stronger conjecture of Erdős and Moser, that the true answer was $\frac{5}{3}n+O(1)$.)

OPEN - $100

Does every convex polygon have a vertex with no other $4$ vertices equidistant from it?

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.

OPEN

Let $h(n)$ be such that any $n$ points in $\mathbb{R}^2$, with no three on a line and no four on a circle, determine at least $h(n)$ distinct distances. Does $h(n)/n\to \infty$?

Erdős could not even prove $h(n)\geq n$. Pach has shown $h(n)<n^{\log_23}$. Erdős, Füredi, and Pach have improved this to
\[h(n) < n\exp(c\sqrt{\log n})\]
for some constant $c>0$.

OPEN - $100

Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points with minimum distance equal to 1, chosen to minimise the diameter of $A$. If $n$ is sufficiently large then must there be three points in $A$ which form an equilateral triangle of size 1?

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

OPEN

Let $A$ be a set of $n$ points in $\mathbb{R}^2$ such that all pairwise distances are at least $1$ and if two distinct distances differ then they differ by at least $1$. Is the diameter of $A$ $\gg n$?

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

OPEN - $100

Given $n$ points in $\mathbb{R}^2$, no five of which are on a line, the number of lines containing four points is $o(n^2)$.

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

OPEN

Let $c>0$ and $h_c(n)$ be such that for any $n$ points in $\mathbb{R}^2$ such that there are $\geq cn^2$ lines each containing more than three points, there must be some line containing $h_c(n)$ many points. Estimate $h_c(n)$. Is it true that, for fixed $c>0$, we have $h_c(n)\to \infty$?

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

OPEN

Let $h(n)$ count the number of incongruent sets of $n$ points in $\mathbb{R}^2$ which minimise the diameter subject to the constraint that $d(x,y)\geq 1$ for all points $x\neq y$. Is it true that $h(n)\to \infty$?

It is not even known whether $h(n)\geq 2$ for all large $n$.

See also [99].

OPEN

Given $n$ points in $\mathbb{R}^2$ the number of distinct unit circles containing at least three points is $o(n^2)$.

OPEN - $50

Let $A,B\subset \mathbb{R}^2$ be disjoint sets of size $n$ and $n-3$ respectively, with not all of $A$ contained on a single line. Is there a line which contains at least two points from $A$ and no points from $B$?

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

OPEN

Draw $n$ squares inside the unit square with no common interior point. Let $f(n)$ be the maximum possible total perimeter of the squares. Is $f(k^2+1)=4k$?

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

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

Let $A\subset \mathbb{R}^2$ be a set of $n$ points such that any subset of size $4$ determines at least $5$ distinct distances. Must $A$ determine $\gg n^2$ many distances?

Erdős also makes the even stronger conjecture that $A$ must contain $\gg n$ many points such that all pairwise distances are distinct.

OPEN

In any $2$-colouring of $\mathbb{R}^2$, for all but at most one triangle $T$, there is a monochromatic congruent copy of $T$.

For some colourings a single equilateral triangle has to be excluded, considering the colouring by alternating strips. Shader [Sh76] has proved this is true if we just consider a single right-angled triangle.

OPEN

A finite set $A\subset \mathbb{R}^n$ is called Ramsey if, for any $k\geq 1$, there exists some $d=d(A,k)$ such that in any $k$-colouring of $\mathbb{R}^d$ there exists a monochromatic copy of $A$. Characterise the Ramsey sets in $\mathbb{R}^n$.

Erdős, Graham, Montgomery, Rothschild, Spencer, and Straus [EGMRSS73] proved that every Ramsey set is 'spherical': it lies on the surface of some sphere. Graham has conjectured that every spherical set is Ramsey. Leader, Russell, and Walters [LRW12] have alternatively conjectured that a set is Ramsey if and only if it is 'subtransitive': it can be embedded in some higher-dimensional set on which rotations act transitively.

Sets known to be Ramsey include vertices of $k$-dimensional rectangles [EGMRSS73], non-degenerate simplices [FrRo90], trapezoids [Kr92], and regular polygons/polyhedra [Kr91].

OPEN

What is the smallest $k$ such that $\mathbb{R}^2$ can be red/blue coloured with no pair of red points unit distance apart, and no $k$-term arithmetic progression of blue points?

Juhász [Ju79] has shown that $k\geq 5$. It is also known that $k\leq 10000000$ (as Erdős writes, 'more or less').

SOLVED

If $\mathbb{R}^2$ is finitely coloured then must there exist some colour class which contains the vertices of a rectangle of every area?

Graham [Gr80] has shown that this is true if we replace rectangle by right-angled triangle. The same question can be asked for parallelograms. It is not true for rhombuses.

This is false; Kovač [Ko23] provides an explicit (and elegantly simple) colouring using 25 colours such that no colour class contains the vertices of a rectangle of area $1$. The question for parallelograms remains open.

OPEN

Let $S\subseteq \mathbb{Z}^3$ be a finite set and let $A=\{a_1,a_2,\ldots,\}\subset \mathbb{Z}^3$ be an infinite $S$-walk, so that $a_{i+1}-a_i\in S$ for all $i$. Must $A$ contain three collinear points?

Originally conjectured by Gerver and Ramsey [GeRa79], who showed that the answer is yes for $\mathbb{Z}^2$, and for $\mathbb{Z}^3$ that the largest number of collinear points can be bounded.

SOLVED

Let $A$ be a finite collection of $d\geq 4$ non-parallel lines in $\mathbb{R}^2$ such that there are no points where at least four lines from $A$ meet. Must there exist a 'Gallai triangle' (or 'ordinary triangle'): three lines from $A$ which intersect in three points, and each of these intersection points only intersects two lines from $A$?

Equivalently, one can ask the dual problem: given $n$ points in $\mathbb{R}^2$ such that there are no lines containing at least four points then there are three points such that the lines determined by them are ordinary ones (i.e. contain exactly two points each).

The Sylvester-Gallai theorem implies that there must exist a point where only two lines from $A$ meet. This problem asks whether there must exist three such points which form a triangle (with sides induced by lines from $A$). Füredi and Palásti [FuPa84] showed this is false when $d\geq 4$ is not divisible by $9$. Escudero [Es16] showed this is false for all $d\geq 4$.

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

OPEN

Is there a dense subset of $\mathbb{R}^2$ such that all pairwise distances are rational?

Conjectured by Ulam. Erdős believed there cannot be such a set. This problem is discussed in a blogpost by Terence Tao, in which he shows that there cannot be such a set, assuming the Bombieri-Lang conjecture. The same conclusion was independently obtained by Shaffaf [Sh18].

Indeed, Shaffaf and Tao actually proved that such a rational distance set must be contained in a finite union of real algebraic curves. Solymosi and de Zeeuw [SdZ10] then proved (unconditionally) that a rational distance set contained in a real algebraic curve must be finite, unless the curve contains a line or a circle.

Ascher, Braune, and Turchet [ABT20] observed that, combined, these facts imply that a rational distance set in general position must be finite (conditional on the Bombieri-Lang conjecture).

OPEN

Let $n\geq 4$. Are there $n$ points in $\mathbb{R}^2$, no three on a line and no four on a circle, such that all pairwise distances are integers?

Anning and Erdős [AnEr45] proved there cannot exist an infinite such set. Harborth constructed such a set when $n=5$. The best construction to date, due to Kreisel and Kurz [KK08], has $n=7$.

Ascher, Braune, and Turchet [ABT20] have shown that there is a uniform upper bound on the size of such a set, conditional on the Bombieri-Lang conjecture. Greenfeld, Iliopoulou, and Peluse [GIP24] have shown (unconditionally) that any such set must be very sparse, in that if $S\subseteq [-N,N]^2$ has no three on a line and no four on a circle, and all pairwise distances integers, then \[\lvert S\rvert \ll (\log N)^{O(1)}.\]

See also [130].

SOLVED

Let $S\subset \mathbb{R}^2$ be such that no two points in $S$ are distance $1$ apart. Must the complement of $S$ contain four points which form a unit square?

The answer is yes, proved by Juhász [Ju79], who proved more generally that the complement of $S$ must contain a congruent copy of any set of four points. This is not true for arbitrarily large sets of points, but perhaps is still true for any set of five points.

SOLVED

Does there exist $S\subseteq \mathbb{R}^2$ such that every set congruent to $S$ (that is, $S$ after some translation and rotation) contains exactly one point from $\mathbb{Z}^2$?

An old question of Steinhaus. Erdős was 'almost certain that such a set does not exist'.

In fact, such a set does exist, as proved by Jackson and Mauldin [JaMa02]. Their construction depends on the axiom of choice.

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.

OPEN

For which $n$ are there $n$ points in $\mathbb{R}^2$, no three on a line and no four on a circle, which determine $n-1$ distinct distances and so that (in some ordering of the distances) the $i$th distance occurs $i$ times?

An example with $n=4$ is an isosceles triangle with the point in the centre. Erdős originally believed this was impossible for $n\geq 5$, but Pomerance constructed a set with $n=5$ (see [Er83c] for a description), and Palásti has proved such sets exist for all $n\leq 8$. Erdős believes this is impossible for all sufficiently large $n$.

OPEN

Let $d\geq 2$ and $n\geq 2$. Let $f_d(n)$ be maximal such that, for any $A\subseteq \mathbb{R}^d$ of size $n$, with diameter $1$, the distance 1 occurs between $f_d(n)$ many pairs of points in $A$. Estimate $f_d(n)$.

SOLVED

If $A\subseteq \mathbb{R}^d$ is any set of $2^d+1$ points then some three points in $A$ determine an obtuse angle.

For $d=2$ this is trivial. For $d=3$ there is an unpublished proof by Kuiper and Boerdijk. The general case was proved by Danzer and Grünbaum [DaGr62].

SOLVED

For $A\subset \mathbb{R}^2$ we define the upper density as
\[\overline{\delta}(A)=\limsup_{R\to \infty}\frac{\lambda(A \cap B_R)}{\lambda(B_R)},\]
where $\lambda$ is the Lebesgue measure and $B_R$ is the ball of radius $R$.

Estimate \[m_1=\sup \overline{\delta}(A),\] where $A$ ranges over all measurable subsets of $\mathbb{R}^2$ without two points distance $1$ apart. In particular, is $m_1\leq 1/4$?

A question of Moser [Mo66]. A lower bound of $m_1\geq \pi/8\sqrt{3}\approx 0.2267$ is given by taking the union of open circular discus of radius $1/2$ at a regular hexagonal lattice suitably spaced aprt. Croft [Cr67] gives a small improvement of $m_1\geq 0.22936$.

The trivial upper bound is $m_1\leq 1/2$, since for any unit vector $u$ the sets $A$ and $A+u$ must be disjoint. Erdős' question was solved by Ambrus, Csiszárik, Matolcsi, Varga, and Zsámboki [ACMVZ23] who proved that $m_1\leq 0.247$.

OPEN

Is there some $c>0$ such that every measurable $A\subseteq \mathbb{R}^2$ of measure $\geq c$ contains the vertices of a triangle of area 1?

Erdős (unpublished) proved that this is true if $A$ has infinite measure, or if $A$ is an unbounded set of positive measure.

OPEN

Let $A\subseteq \mathbb{R}^2$ be a measurable set with infinite measure. Must $A$ contain the vertices of an isosceles trapezoid of area $1$?

Erdős and Mauldin (unpublished) claim that this is true for trapezoids in general, but fails for parallelograms.

SOLVED

What is the size of the largest $A\subseteq \mathbb{R}^n$ such that there are only two distinct distances between elements of $A$? That is,
\[\# \{ \lvert x-y\rvert : x\neq y\in A\} = 2.\]

Asked to Erdős by Coxeter. Erdős thought he could show that $\lvert A\rvert \leq n^{O(1)}$, but later discovered a mistake in his proof, and his proof only gave $\leq \exp(n^{1-o(1)})$.

Bannai, Bannai, and Stanton [BBS83] have proved that \[\lvert A\rvert \leq \binom{n+2}{2}.\] A simple proof of this upper bound was given by Petrov and Pohoata [PePo21].

Shengtong Zhang has observed that a simple lower bound of $\binom{n}{2}$ is given by considering all points with exactly two coordinates equal to $1$ and all others equal to $0$.

OPEN

What is the size of the largest $A\subseteq \mathbb{R}^n$ such that every three points from $A$ determine an isosceles triangle? That is, for any three points $x,y,z$ from $A$, at least two of the distances $\lvert x-y\rvert,\lvert y-z\rvert,\lvert x-z\rvert$ are equal.

When $n=2$ the answer is $6$ (due to Kelly [ErKe47]). When $n=3$ the answer is $8$ (due to Croft [Cr62]). The best upper bound known in general is due to Blokhuis [Bl84] who showed that
\[\lvert A\rvert \leq \binom{n+2}{2}.\]

Alweiss has observed a lower bound of $\binom{n+1}{2}$ follows from considering the subset of $\mathbb{R}^{n+1}$ formed of all vectors $e_i+e_j$ where $e_i,e_j$ are distinct coordinate vectors. This set can be viewed as a subset of some $\mathbb{R}^n$, and is easily checked to have the required property.

The fact that the truth for $n=3$ is $8$ suggests that neither of these bounds is the truth.

SOLVED

Let $\alpha_n$ be the infimum of all $0\leq \alpha\leq \pi$ such that in every set $A\subset \mathbb{R}^2$ of size $n$ there exist three distinct points $x,y,z\in A$ such that the angle determined by $xyz$ is at least $\alpha$. Determine $\alpha_n$.

Blumenthal's problem. Szekeres [Sz41] showed that
\[\alpha_{2^n+1}> \pi \left(1-\frac{1}{n}+\frac{1}{n(2^n+1)^2}\right)\]
and
\[\alpha_{2^n}\leq \pi\left(1-\frac{1}{n}\right).\]
Erdős and Szekeres [ErSz60] showed that
\[\alpha_{2^n}=\alpha_{2^n-1}= \pi\left(1-\frac{1}{n}\right),\]
and suggested that perhaps $\alpha_{N}=\pi(1-1/n)$ for $2^{n-1}<N\leq 2^n$. This was disproved by Sendov [Se92].

Sendov [Se93] provided the definitive answer, proving that $\alpha_N=\pi(1-1/n)$ for $2^{n-1}+2^{n-3}<N\leq 2^n$ and $\alpha_N=\pi(1-\frac{1}{2n-1})$ for $2^{n-1}<N\leq 2^{n-1}+2^{n-3}$.

SOLVED

Is every set of diameter $1$ in $\mathbb{R}^n$ the union of at most $n+1$ sets of diameter $<1$?

Borsuk's problem. This is trivially true for $n=1$ and easy for $n=2$. For $n=3$ it is true, which was proved by Eggleston [Eg55].

The answer is in fact no in general, as shown by Kahn and Kalai [KaKa93], who proved that it is false for $n>2014$. The current smallest $n$ where Borsuk's conjecture is known to be false is $n=64$, a result of Brouwer and Jenrich [BrJe14].

If $\alpha(n)$ is the smallest number of pieces of diameter $<1$ required (so Borsuk's original conjecture was that $\alpha(n)=n+1$) then Kahn and Kalai's construction shows that $\alpha(n)\geq (1.2)^{\sqrt{n}}$. The best upper bound, due to Schramm [Sc88], is that \[\alpha(n) \leq ((3/2)^{1/2}+o(1))^{n}.\]

OPEN

What is the minimum number of circles determined by any $n$ points in $\mathbb{R}^2$, not all on a circle?

OPEN

Let $\alpha(n)$ be such that every set of $n$ points in the unit circle contains three points which determine a triangle of area at most $\alpha(n)$. Estimate $\alpha(n)$.

Heilbronn's triangle problem. It is trivial that $\alpha(n) \ll 1/n$. Erdős observed that $\alpha(n)\gg 1/n^2$. The current best bounds are
\[\frac{\log n}{n^2}\ll \alpha(n) \ll \frac{1}{n^{8/7+1/2000}}.\]
The lower bound is due to Komlós, Pintz, and Szemerédi [KPS82]. The upper bound is due to Cohen, Pohoata, and Zakharov [CPZ23] (improving on an exponent of $8/7$ due to Komlós, Pintz, and Szemerédi [KPS81]).

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 $a_n\geq 0$ with $a_n\to 0$ and $\sum a_n=\infty$. Find a necessary and sufficient condition on the $a_n$ such that, if we choose (independently and uniformly) random arcs on the unit circle of length $a_n$, then all the circle is covered with probability $1$.

A problem of Dvoretzky [Dv56]. It is easy to see that (under the given conditions alone) almost all the circle is covered with probability $1$.

Kahane [Ka59] showed that $a_n=\frac{1+c}{n}$ with $c>0$ has this property, which Erd\H{s} (unpublished) improved to $a_n=\frac{1}{n}$. Erd\{o}s also showed that $a_n=\frac{1-c}{n}$ with $c>0$ does not have this property.

Solved by Shepp [Sh72], who showed that a necessary and sufficient condition is that \[\sum_n \frac{e^{a_1+\cdots+a_n}}{n^2}=\infty.\]

OPEN

Let $f(n,k)$ count the number of self-avoiding walks of $n$ steps (beginning at the origin) in $\mathbb{Z}^k$ (i.e. those walks which do not intersect themselves). Determine
\[C_k=\lim_{n\to\infty}f(n,k)^{1/n}.\]

The constant $C_k$ is sometimes known as the connective constant. Hammersley and Morton [HM54] showed that this limit exists, and it is trivial that $k\leq C_k\leq 2k-1$.

Kesten [Ke63] proved that $C_k=2k-1-1/2k+O(1/k^2)$, and more precise asymptotics are given by Clisby, Liang, and Slade [CLS07].

Conway and Guttmann [CG93] showed that $C_2\geq 2.62$ and Alm [Al93] showed that $C_2\leq 2.696$.

OPEN

Let $d_k(n)$ be the expected distance from the origin after taking $n$ random steps from the origin in $\mathbb{Z}^k$ (conditional on no self intersections). Is it true that
\[\lim_{n\to \infty}\frac{d_2(n)}{n^{1/2}}= \infty?\]
Is it true that
\[d_k(n)\ll n^{1/2}\]
for $k\geq 3$?

OPEN - $100

Let $f_k(n)$ be minimal such that if $n$ points in $\mathbb{R}^2$ have no $k+1$ points on a line then there must be at most $f_k(n)$ many lines containing at least $k$ points. Is it true that
\[f_k(n)=o(n^2)\]
for $k\geq 4$?

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})}\]

OPEN

Let $g(n)$ be maximal such that in any set of $n$ points in $\mathbb{R}^2$ with no four points on a line there exists a subset on $g(n)$ points with no three points on a line. Estimate $g(n)$.

The trivial greedy algorithm gives $g(n)\gg n^{1/2}$. A similar question can be asked for a set with no $k$ points on a line, searching for a subset with no $l$ points on a line, for any $3\leq l<k$.

Erdős thought that $g(n) \gg n$, but in fact $g(n)=o(n)$, which follows from the density Hales-Jewett theorem proved by Furstenberg and Katznelson [FuKa91] (see [185]).

OPEN - $500

Given $n$ distinct points $A\subset\mathbb{R}^2$ must there be a point $x\in A$ such that
\[\#\{ d(x,y) : y \in A\} \gg n^{1-o(1)}?\]
Or even $\gg n/\sqrt{\log n}$?

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

SOLVED

Is there some function $f(n)\to \infty$ as $n\to\infty$ such that there exist $n$ distinct points on the surface of a two-dimensional sphere with at least $f(n)n$ many pairs of points whose distances are the same?

See also [90]. This was solved by Erdős, Hickerson, and Pach [EHP89]. For $D>1$ and $n\geq 2$ let $u_D(n)$ be such that there is a set of $n$ points on the sphere in $\mathbb{R}^3$ with radius $D$ such that there are $u_D(n)$ many pairs which are distance $1$ apart (so that this problem asked for $u_D(n)\geq f(n)n$ for some $D$).

Erdős, Hickerson, and Pach [EHP89] proved that $u_{\sqrt{2}}(n)\asymp n^{4/3}$ and $u_D(n)\gg n\log^*n$ for all $D>1$ and $n\geq 2$ (where $\log^*$ is the iterated logarithm function).

This lower bound was improved by Swanepoel and Valtr [SwVa04] to $u_D(n) \gg n\sqrt{\log n}$. The best upper bound for general $D$ is $u_D(n)\ll n^{4/3}$.

SOLVED

Given any $n$ distinct points in $\mathbb{R}^2$ let $f(n)$ count the number of distinct lines determined by these points. What are the possible values of $f(n)$?

A question of Grünbaum. The Sylvester-Gallai theorem implies that if $f(m)>1$ then $f(m)\geq n$. Erdős showed that, for some constant $c>0$, all integers in $[cn^{3/2},\binom{n}{2}]$ are possible except $\binom{n}{2}-1$ and $\binom{n}{2}-3$.

Solved (for all sufficiently large $n$) completely by Erdős and Salamon [ErSa88]; the full description is too complicated to be given here.

OPEN - $250

For a set of $n$ points $P\subset \mathbb{R}^2$ let $\ell_1,\ldots,\ell_m$ be the lines determined by $P$, and let $A=\{\lvert \ell_1\cap P\rvert,\ldots,\lvert \ell_m\cap P\rvert\}$.

Let $F(n)$ count the number of possible sets $A$ that can be constructed this way. Is it true that \[F(n) \leq \exp(O(\sqrt{n}))?\]

Erdős writes it is 'easy to see' that this bound would be best possible.

OPEN - $25

Classify those triangles which can only be cut into a square number of congruent triangles.

Erdős' question was reported by Soifer [So09c]. It is easy to see (see for example [So09]) that any triangle can be cut into $n^2$ congruent triangles (for any $n\geq 1$). Soifer [So09b] proved that there exists at least one triangle (e.g. one with sides $\sqrt{2},\sqrt{3},\sqrt{4}$) which can only be cut into a square number of congruent triangles. (In fact Soifer proves that any triangle for which the angles and sides are both integrally independent has this property.)

Soifer proved [So09] that if we relax congruence to similarity then every triangle can be cut into $n$ similar triangles when $n\neq 2,3,5$ and there exists a triangle that cannot be cut into $2$, $3$, or $5$ similar triangles.

See also [634].

OPEN - $25

Find all $N$ such that there is at least one triangle which can be cut into $n$ congruent triangles.

Erdős' question was reported by Soifer [So09c]. It is easy to see that all square numbers have this property (in fact for square numbers any triangle will do). Soifer [So09c] has shown that numbers of the form $2n^2,3n^2,6n^2,n^2+m^2$ also have this property. Beeson has shown (see the slides below) that $7$ and $11$ do not have this property. It is possible than any prime of the form $4n+3$ does not have this property.

In particular, it is not known if $19$ has this property (i.e. are there $19$ congruent triangles which can be assembled into a triangle?).

For more on this problem see these slides from a talk by Michael Beeson. As a demonstration of this problem we include a picture of a cutting of an equilateral triangle into $27$ congruent triangles from these slides.

Soifer proved [So09] that if we relax congruence to similarity then every triangle can be cut into $N$ similar triangles when $N\neq 2,3,5$.

If one requires the smaller triangles to be similar to the larger triangle then the only possible values of $N$ are $n^2,n^2+m^2,3n^2$, proved by Snover, Waiveris, and Williams [SWW91].

See also [633].

SOLVED

Let $f_k(n)$ denote the smallest integer such that any $f_k(n)$ points in general position in $\mathbb{R}^k$ contain at $n$ which determine a convex polyhedron. Is it true that
\[f_k(n) > (1+c_k)^n\]
for some constant $c_k>0$?

The function when $k=2$ is the subject of the Erdős-Klein-Szekeres conjecture, see [107]. One can show that
\[f_2(n)>f_3(n)>\cdots.\]
The answer is no, even for $k=3$: Pohoata and Zakharov [PoZa22] have proved that
\[f_3(n)\leq 2^{o(n)}.\]

OPEN

Let $x_1,\ldots,x_n\in \mathbb{R}^2$ and let $R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}$, where the points are ordered such that
\[R(x_1)\leq \cdots \leq R(x_n).\]
Let $\alpha_k$ be minimal such that, for all large enough $n$, there exists a set of $n$ points with $R(x_k)<\alpha_kn^{1/2}$. Is it true that $\alpha_k\to \infty$ as $k\to \infty$?

It is trivial that $R(x_1)=1$ is possible, and that $R(x_2) \ll n^{1/2}$ is also possible, but we always have
\[R(x_1)R(x_2)\gg n.\]
Erdős originally conjectured that $R(x_3)/n^{1/2}\to \infty$ as $n\to \infty$, but Elekes proved that for every $k$ and $n$ sufficiently large there exists some set of $n$ points with $R(x_k)\ll_k n^{1/2}$.

OPEN

Let $x_1,\ldots,x_n\in \mathbb{R}^2$ and let $R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}$, where the points are ordered such that
\[R(x_1)\leq \cdots \leq R(x_n).\]
Let $g(n)$ be the maximum number of distinct values the $R(x_i)$ can take. Is it true that $g(n) \geq (1-o(1))n$?

Erdős and Fishburn proved $g(n)>\frac{3}{9}n$ and Csizmadia proved $g(n)>\frac{7}{10}n$. Both groups proved $g(n) < n-cn^{2/3}$ for some constant $c>0$.

OPEN

Let $x_1,\ldots,x_n\in \mathbb{R}^2$ be such that no circle whose centre is one of the $x_i$ contains three other points. Are there at least
\[(1+c)\frac{n}{2}\]
distinct distances determined between the $x_i$, for some constant $c>0$ and all $n$ sufficiently large?

A problem of Erdős and Pach. It is easy to see that this assumption implies that there are at least $\frac{n-1}{2}$ distinct distances determined by every point.

OPEN

Is it true that if $A\subset \mathbb{R}^2$ is a set of $n$ points such that every subset of $4$ points determines at least $5$ distances then $A$ must determine $\gg n^2$ distances?

A problem of Erdős and Gyárfás. Erdős could not even prove that the number of distances is at least $f(n)n$ where $f(n)\to \infty$.

More generally, one can ask how many distances $A$ must determine if every set of $p$ points determines at least $q$ points.

See also [657].

OPEN

Is it true that if $A\subset \mathbb{R}^2$ is a set of $n$ points such that every subset of $3$ points determines $3$ distinct distances (i.e. $A$ has no isosceles triangles) then $A$ must determine at least $f(n)n$ distinct distances, for some $f(n)\to \infty$?

In [Er73] Erdős attributes this problem (more generally in $\mathbb{R}^k$) to himself and Davies. In [Er97e] he does not mention Davis, but says this problem was investigated by himself, Füredi, Ruzsa, and Pach.

In [Er73] Erdős says it is not even known in $\mathbb{R}$ whether $f(n)\to \infty$. Straus has observed that if $2^k\geq n$ then there exist $n$ points in $\mathbb{R}^k$ which contain no isosceles triangle and determine at most $n-1$ distances.

See also [656].

OPEN

Is there a set of $n$ points in $\mathbb{R}^2$ such that every subset of $4$ points determines at least $3$ distances, yet the total number of distinct distances is
\[\ll \frac{n}{\sqrt{\log n}}?\]

Erdős believed this should be possible, and should imply effective upper bounds for [658] (presumably the version with no alignment restrictions on the squares).

OPEN

Let $x_1,\ldots,x_n\in \mathbb{R}^3$ be the vertices of a convex polyhedron. Is there some constant $c>0$ such that, for all $n$ sufficiently large, the number of distinct distances determined by the $x_i$ is at most
\[(1-c)\frac{n}{2}?\]

OPEN

Are there, for all large $n$, some points $x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^2$ such that the number of distinct distances $d(x_i,y_j)$ is
\[o\left(\frac{n}{\sqrt{\log n}}\right)?\]

One can also ask this for points in $\mathbb{R}^3$. In $\mathbb{R}^4$ Lenz observed that there are $x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^4$ such that $d(x_i,y_j)=1$ for all $i,j$, taking the points on two orthogonal circles.

More generally, if $F(2n)$ is the minimal number of such distances, and $f(2n)$ is minimal number of distinct distances between any $2n$ points in $\mathbb{R}^2$, then is $f \ll F$?

See also [89].

OPEN

Consider the triangular lattice with minimal distance between two points $1$. Denote by $f(t)$ the number of distances from any points $\leq t$. For example $f(1)=6$, $f(\sqrt{3})=12$, and $f(3)=18$.

Let $x_1,\ldots,x_n\in \mathbb{R}^2$ be such that $d(x_i,x_j)\geq 1$ for all $i\neq j$. Is it true that, provided $n$ is sufficiently large depending on $t$, the number of distances $d(x_i,x_j)\leq t$ is less than or equal to $f(t)$ with equality perhaps only for the triangular lattice?

In particular, is it true that the number of distances $\leq \sqrt{3}-\epsilon$ is less than $1$?

A problem of Erdős, Lovász, and Vesztergombi.

This is essentially verbatim the problem description in [Er97e], but this does not make sense as written; there must be at least one typo. Suggestions about what this problem intends are welcome.

Erdős also goes on to write 'Perhaps the following stronger conjecture holds: Let $t_1<t_2<\cdots$ be the set of distances occurring in the triangular lattice. $t_1=1$ $t_2=\sqrt{3}$ $t_3=3$ $t_4=5$ etc. Is it true that there is an $\epsilon_n$ so that for every set $y_1,\ldots,$ with $d(y_i,y_j)\geq 1$ the number of distances $d(y_i,y_j)<t_n$ is less than $f(t_n)$?'

Again, this is nonsense interpreted literally; I am not sure what Erdős intended.

OPEN

Let $F_k(n)$ be minimal such that for any $n$ points in $\mathbb{R}^2$ there exist at most $F_k(n)$ many distinct lines passing through at least $k$ of the points, and $f_k(n)$ similarly but with lines passing through exactly $k$ points.

Estimate $f_k(n)$ and $F_k(n)$ - in particular, determine $\lim F_k(n)/n^2$ and $\lim f_k(n)/n^2$.

Trivially $f_k(n)\leq F_K(n)$ and $f_2(n)=F_2(n)=\binom{n}{2}$. The problem with $k=3$ is the classical 'Orchard problem' of Sylvester. Burr, Grünbaum, and Sloane [BGS74] have proved that
\[f_3(n)=\frac{n^2}{6}-O(n)\]
and
\[F_3(n)=\frac{n^2}{6}-O(n).\]
There is a trivial upper bound of $F_k(n) \leq \binom{n}{2}/\binom{k}{2}$, and hence
\[\lim F_k(n)/n^2 \leq \frac{1}{k(k-1)}.\]

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

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

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 $f(n)$ be maximal such that there exists a set $A$ of $n$ points in $\mathbb{R}^4$ in which every $x\in A$ has at least $f(n)$ points in $A$ equidistant from $x$.

Is it true that $f(n)\leq \frac{n}{2}+O(1)$?

Erdős, Makai, and Pach proved that
\[\frac{n}{2}+2 \leq f(n) \leq (1+o(1))\frac{n}{2}.\]

See also [753].

OPEN

The number of equilateral triangles of size $1$ formed by any set of $3n$ points in $\mathbb{R}^6$ is at most $(1+o(1))n^3$.

A construction of Lenz shows that, when $4\mid n$, it is possible to form $n^3+6n^2$ many equilateral triangles of size $1$: take three suitable orthogonal circles and take $n$ points on each of them which form $n/4$ inscribed squares.

Erdős further believes this upper bound should hold even if we count equilateral triangles of any size.

SOLVED

Let $A\subset \mathbb{R}^2$ be a set of $n$ points. Can there be $\gg n$ many distinct distances each of which occurs for more than $n$ many pairs from $A$?

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 (see [132]).

The answer is yes: Bhowmick [Bh24] constructs a set of $n$ points in $\mathbb{R}^2$ such that $\lfloor\frac{n}{4}\rfloor$ distances occur at least $n+1$ times. More generally, they construct, for any $m$ and large $n$, a set of $n$ points such that $\lfloor \frac{n}{2(m+1)}\rfloor$ distances occur at least $n+m$ times.

OPEN

Let $A\subset \mathbb{R}_{>0}$ be a set of size $n$ such that every subset $B\subseteq A$ with $\lvert B\rvert =4$ has $\lvert B-B\rvert\geq 11$. Find the best constant $c>0$ such that $A$ must always contain a Sidon set of size $\geq cn$.

For comparison, note that if $B$ were a Sidon set then $\lvert B-B\rvert=13$, so this condition is saying that at most one difference is 'missing' from $B-B$. Equivalently, one can view $A$ as a set such that every four points determine at least five distinct distances, and ask for a subset with all distances distinct.

Erdős and Sós proved that $c\geq 1/2$. Gyárfás and Lehel [GyLe95] proved \[\frac{1}{2}<c<\frac{3}{5}.\] (The example proving the upper bound is the set of the first $n$ Fibonacci numbers.)

OPEN

Let $c(n)$ be minimal such that if $k\geq c(n)$ then the $n$-dimensional unit cube can be decomposed into $k$ homothetic $n$-dimensional cubes. Give good bounds for $c(n)$ - in particular, is it true that $c(n) \gg n^n$?

A problem first investigated by Hadwiger, who proved the lower bound
\[c(n) \geq 2^n+2^{n-1}.\]
It is easy to see that $c(2)=6$. Meier conjectured $c(3)=48$. Burgess and Erdős [Er74b] proved
\[c(n) \ll n^{n+1}.\]
Erdős wrote 'I am certain that if $n+1$ is a prime then $c(n)>n^n$.'.

SOLVED

Let $t(n)$ be the minimum number of points in $\{1,\ldots,n\}^2$ such that the $\binom{t}{2}$ lines determined by these points cover all points in $\{1,\ldots,n\}^2$.

Estimate $t(n)$. In particular, is it true that $t(n)=o(n)$?

A problem of Erdős and Purdy, who proved $t(n) \gg n^{2/3}$.

Resolved by Alon [Al91] who proved $t(n) \ll n^{2/3}\log n$.