Logo
All Solved All Open Random Solved Random Open
14 solved out of 48 shown
$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 possibe. Nearly solved by Guth and Katz [GuKa15] who proved that there are always $\gg n/\log n$ many distinct distances. It may be true that there is a single point which determines $\gg n/\sqrt{\log n}$ distinct distances, or even that there are $\gg n$ many such points, or even that this is true averaged over all points.
$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?
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 [SpSzTr84]. In [Er83c] Erdős offers \$250 for an upper bound of the form $n^{1+o(1)}$.
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').
$500
Let $\epsilon>0$. Given any set of $n$ distinct points in $\mathbb{R}^2$ prove that each point is equidistant from $O_\epsilon(n^\epsilon)$ many other points.
Erdős only offers \$100 for a counterexample.
If $n$ distinct points in $\mathbb{R}^2$ form a convex polygon then they determine at least $\lfloor n/2\rfloor$ distinct distances.
Solved by Altman [Al63]. The stronger variant that says there is one point which determines at least $\lfloor n/2\rfloor$ distinct distances is still open.
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 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.
$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}.\]
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.\]
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 has proved an upper bound of $O(n\log n)$. Edelsbrunner and Hajnal have constructed $n$ such points with $2n-7$ pairs distance $1$ apart.
Does every polygon have a vertex with no other $4$ vertices equidistant from it?
Open even for convex polygons.

Danzer has 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 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?

Additional thanks to: Boris Alexeev and Dustin Mixon
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}$.
$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?
In fact Erdős believed such a set must have very large intersection with the triangular lattice. This is false for $n=4$, for example a square. The behaviour of such sets for small $n$ is explored by Bezdek and Fodor [BeFo99].
Additional thanks to: Boris Alexeev and Dustin Mixon
Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points with distance set $D=\{\lvert x-y\rvert : x\neq y \in A\}$. Suppose that if $d_1\neq d_2\in D$ then $\lvert d_1-d_2\rvert \geq 1$. Is there some constant $c>0$ such that the diameter of $A$ must be at least $cn$?
Perhaps the diameter is $\geq n-1$ for all large $n$ (Piepmeyer has an example of $9$ such points with diameter $<5$).
Additional thanks to: Shengtong Zhang
$100
Given $n$ points in $\mathbb{R}^2$, no five of which are on a line, then the number of lines containing four points is $o(n^2)$.
An example of Grünbaum shows that there could be $\gg n^{3/2}$ such lines. This may be the correct order of magnitude.
Given $n$ points in $\mathbb{R}^2$ such that there are $\geq cn^2$ lines each containing more than three points there must be a single line containing $\gg_c n^{1/2}$ many points.
Even replacing $n^{1/2}$ with any function $\to\infty$, this conjecture is 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$. 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$.
Additional thanks to: Boris Alexeev and Dustin Mixon
Given $n$ points in $\mathbb{R}^2$ the number of distinct unit circles containing at least three points is $o(n^2)$.
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.
$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] implies it is true with $n-3$ replaced by $cn$ for some constant $c>0$.
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$?
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)$.
$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})}.\]

See also the entry in the graphs problem collection.

Additional thanks to: Casey Tompkins
$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.
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.
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].

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

Additional thanks to: Ryan Alweiss, Vjekoslav Kovac
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}^3$, and for $\mathbb{Z}^2$ that the number of collinear points can be bounded.
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': three lines from $A$ which intersect in three points, and each of these intersection points only intersects two lines from $A$?
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$.
Additional thanks to: Juan Escudero
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 intersect exactly 2 points. Does $f(n)\to \infty$? How fast?
Conjectured by Erdős and de Bruijn. The Sylvester-Gallai theorem states that $f(n)\geq 1$. 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$.
$100
Let $1\leq k<n$. Given $n$ points in $\mathbb{R}^2$, at most $n-k$ on any line, the number of distinct lines formed joining two points is $\gg kn$.
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].
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).

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?
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, hten \[\lvert S\rvert \ll (\log N)^{O(1)}.\]

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.
Additional thanks to: Bhavik Mehta
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.

Additional thanks to: Vjekoslav Kovac
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, 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$.

See also the entry in the graphs problem collection.

Additional thanks to: Zachary Hunter
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 'a Hungarian high school student' gave an unspecified construction for $n=6$. Is this possible for $n=7$?
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)$.
Hopf and Pannwitz [HoPa34] proved $f_2(n)=n$. Heppes [He56] and Grünbaum-Strasziewicz independently showed that $f_3(n)=2n-2$.
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].
Additional thanks to: Boris Alexeev and Dustin Mixon
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.
Additional thanks to: Vjekoslav Kovac
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.
Additional thanks to: Vjekoslav Kovac
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)})$.
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}.\]
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}$.

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 (\sqrt{3/2}+o(1))^{n}.\] The true order of magnitude may be $\alpha(n)=c^n$ for some $c>1$.

What is the minimum number of circles determined by any $n$ points in $\mathbb{R}^2$, not all on a circle?
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]).
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$.
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.\]

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

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