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 - for example, if $d(x)$ counts the number of distinct distances from $x$ then in [Er75f] Erdős conjectured\[\sum_{x\in A}d(x) \gg \frac{n^2}{\sqrt{\log n}},\]where $A\subset \mathbb{R}^2$ is any set of $n$ points.

See also [661], and [1083] for the generalisation to higher dimensions.

View the LaTeX source

This page was last edited 15 October 2025.

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

This would be the best possible, as is shown by a set of lattice points. It is easy to show that there are $O(n^{3/2})$ many such pairs. The best known upper bound is $O(n^{4/3})$, due to Spencer, Szemerédi, and Trotter [SST84]. In [Er83c] and [Er85] Erdős offers \$250 for an upper bound of the form $n^{1+o(1)}$.

Part of the difficulty of this problem is explained by a result of Valtr (see [Sz16]), who constructed a metric on $\mathbb{R}^2$ and a set of $n$ points with $\gg n^{4/3}$ unit distance pairs (with respect to this metric). The methods of the upper bound proof of Spencer, Szemerédi, and Trotter [SST84] generalise to include this metric. Therefore to prove an upper bound better than $n^{4/3}$ some special feature of the Euclidean metric must be exploited.

See a survey by Szemerédi [Sz16] for further background and related results.

See also [92], [96], [605], and [956]. The higher dimensional generalisation is [1085].

View the LaTeX source

This page was last edited 15 October 2025.

For $n=3$ the equilateral triangle is the only such set. For $n=4$ the square or two equilateral triangles sharing an edge give two non-similar examples.

For $n=5$ the regular pentagon is the unique such set (which has two distinct distances). Erdős mysteriously remarks in [Er90] this was proved by 'a colleague'. (In [Er87b] this is described as 'a colleague from Zagreb (unfortunately I do not have his letter)'.) A published proof of this fact is provided by Kovács [Ko24c].

In [Er87b] Erdős says that there are at least two non-similar examples for $6\leq n\leq 9$.

The minimal possible number of distinct distances is the subject of [89].

View the LaTeX source

This page was last edited 16 January 2026.

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. This latter prize is downgraded to \$50 in [ErFi97].

It is trivial that $f(n) \ll n^{1/2}$. A result of Pach and Sharir (Theorem 4 of [PaSh92]) implies $f(n) \ll n^{2/5}$. Hunter has observed that the circle-point incidence bound of Janzer, Janzer, Methuku, and Tardos [JJMT24] implies\[f(n) \ll n^{4/11}.\]Fishburn (personal communication to Erdős, later published in [ErFi97]) 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].

View the LaTeX source

This page was last edited 28 December 2025.

Solved by Altman [Al63]. The stronger variant that says there is one point which determines at least $\lfloor \frac{n}{2}\rfloor$ distinct distances (see [982]) 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 a stronger form in which the convexity is replaced by the assumption that there are no three points on a line - see [1082].

See also [660].

View the LaTeX source

This page was last edited 19 October 2025.

In [Er97c] Erdős claims that Fishburn solved this, but gives no reference. Note it is trivial that $\sum f(u_i)=\binom{n}{2}$.

Lefmann and Theile [LeTh95] prove a stronger version of this question, that\[\sum_i f(u_i)^2 \ll n^3\]under the weaker assumption that no three points are on a line. A sketch of this proof is given in the comments by serge.

Erdős and Fishburn also make the stronger conjecture that $\sum f(u_i)^2$ is maximal for the regular $n$-gon (for large enough $n$).

In [Er92e] Erdős offered £25 for a resolution of this problem. (This has been converted to $44 using approximate 1992 exchange rates.)

See also [95].

View the LaTeX source

This page was last edited 28 December 2025.

The case when the points determine a convex polygon was 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].

View the LaTeX source

Conjectured by Erdős and Moser. In [Er92e] Erdős credits the conjecture that the true upper bound is $2n$ to himself and Fishburn. 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)$.)

A positive answer would follow from [97]. See also [90].

In [Er92e] Erdős makes the stronger conjecture that, if $g(x)$ counts the largest number of points equidistant from $x$ in $A$, then\[\sum_{x\in A}g(x)< 4n.\]He notes that the example of Edelsbrunner and Hajnal shows that $\sum_{x\in A}g(x)>4n-O(1)$ is possible.

View the LaTeX source

Erdős originally conjectured this (in [Er46b]) 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). Danzer's construction is explained in [Er87b]. 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? In [Er75f] Erdős claimed that Danzer proved that this false for every constant - in fact, for any $k$ there is a convex polygon such that every vertex has $k$ vertices equidistant from it. Since this claim was not repeated in later papers, presumably Erdős was mistaken here.

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.

View the LaTeX source

This page was last edited 27 October 2025.

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

View the LaTeX source

This page was last edited 15 October 2025.

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

View the LaTeX source

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

View the LaTeX source

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] and [669]. A generalisation of this problem is asked in [588].

This problem is Problem 71 on Green's open problems list.

View the LaTeX source

This page was last edited 27 December 2025.

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 at one point [Er95] 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)}$.

View the LaTeX source

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

See also [99].

View the LaTeX source

In [Er81d] Erdős proved that $\gg n$ many circles is possible, and that there cannot be more than $O(n^2)$ many circles. The argument is very simple: every pair of points determines at most $2$ unit circles, and the claimed bound follows from double counting. Erdős claims in a number of places this produces the upper bound $n(n-1)$, but Harborth and Mengerson [HaMe86] note that in fact this delivers an upper bound of $\frac{n(n-1)}{3}$.

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] and [Er92e] Erdős also asks how many such unit circles there must be if the points are in general position.

In [Er92e] Erdős offered £100 for a proof or disproof that the answer is $O(n^{3/2})$.

The maximal number of unit circles achieved by $n$ points is A003829 in the OEIS.

See also [506] and [831].

View the LaTeX source

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

This has been disproved by Xichuan in the comments, who has found three explicit counterexamples. It remains possible that this holds with $n-4$ (or in general with $n-O(1)$ or $(1-o(1))n$).

View the LaTeX source

This page was last edited 25 October 2025.

In [Er94b] Erdős dates this conjecture to 'more than 60 years ago'. Erdős proved that $f(2)=1$ in an early mathematical paper for high school students in Hungary. Newman proved (in personal communication to Erdős) that $f(5)=2$.

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

It is easy to see that $f(k^2+1)\geq k$, by first dividing the unit square into $k^2$ smaller squares of side-length $1/k$, and then replacing one square by two smaller squares of side-length $1/2k$. Halász [Ha84] gives a construction that shows $f(k^2+2)\geq k+\frac{1}{k+1}$, and in general, for any $c\geq 1$,\[f(k^2+2c+1)\geq k+\frac{c}{k}\]and\[f(k^2+2c)\geq k+\frac{c}{k+1}.\]Halász also considers the variants where we replace a square by a parallelogram or triangle.

Erdős and Soifer [ErSo95] and Campbell and Staton [CaSt05] have conjectured that, in general, for any integer $-k<c<k$, $f(k^2+2c+1)=k+\frac{c}{k}$, and proved the corresponding lower bound. Praton [Pr08] has proved that this general conjecture is equivalent to $f(k^2+1)=k$.

Baek, Koizumi, and Ueoro [BKU24] have proved $g(k^2+1)=k$, where $g(\cdot)$ is defined identically to $f(\cdot)$ with the additional assumption that all squares have sides parallel to the sides of the unit square. More generally, they prove that $g(k^2+2c+1)=k+c/k$ for any $-k<c<k$, which determines all values of $g(\cdot)$.

View the LaTeX source

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

View the LaTeX source

This page was last edited 28 December 2025.

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$. Erdős [Er97b] also makes the even stronger conjecture that $A$ must contain $\gg n$ many points such that all pairwise distances are distinct.

Answered in the negative by Tao [Ta24c], who proved that for any large $n$ there exists a set of $n$ points in $\mathbb{R}^2$ such that any four points determine at least five distinct distances, yet there are $\ll n^2/\sqrt{\log n}$ distinct distances in total. Tao discusses his solution in a blog post.

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

See also [136], [657], and [659].

View the LaTeX source

This page was last edited 16 January 2026.

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.

View the LaTeX source

This page was last edited 16 October 2025.

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

View the LaTeX source

This page was last edited 16 October 2025.

Erdős, Graham, Montgomery, Rothschild, Spencer, and Straus [EGMRSS75] proved $k\geq 5$. Tsaturian [Ts17] improved this to $k\geq 6$. Erdős and Graham claim that $k\leq 10000000$ ('more or less'), but give no proof.

Erdős and Graham asked this with just any $k$-term arithmetic progression in blue (not necessarily with distance $1$), but Alon has pointed out that in fact no such $k$ exists: in any red/blue colouring of the integer points on a line either there are two red points distance $1$ apart, or else the set of blue points and the same set shifted by $1$ cover all integers, and hence by van der Waerden's theorem there are arbitrarily long blue arithmetic progressions.

It seems most likely, from context, that Erdős and Graham intended to restrict the blue arithmetic progression to have distance $1$ (although they do not write this restriction in their papers).

View the LaTeX source

This page was last edited 14 October 2025.

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.

This problem has been formalised in Lean as part of the Google DeepMind Formal Conjectures project.

View the LaTeX source

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.

View the LaTeX source

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

See also [960].

View the LaTeX source

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 (and sufficiently large) then $f(n)\geq 3\lfloor n/4\rfloor$.

View the LaTeX source

This page was last edited 16 October 2025.

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

View the LaTeX source

This page was last edited 16 October 2025.

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

In [Er87b] Erdős mentions that Besicovitch conjectured that the limit points of a rational distance set cannot contain arbitrarily large convex sets.

View the LaTeX source

This page was last edited 16 October 2025.

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

View the LaTeX source

This page was last edited 16 October 2025.

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.

View the LaTeX source

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.

View the LaTeX source

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

Heule and Scheucher [HeSc24] have proved that $g(6)=30$.

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

View the LaTeX source

This page was last edited 30 December 2025.

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 believed this is impossible for all sufficiently large $n$. This would follow from $h(n)\geq n$ for sufficiently large $n$, where $h(n)$ is as in [98].

View the LaTeX source

This page was last edited 02 October 2025.

In [Er46b] Erdős says this was a conjecture of Vázsonyi.

• Hopf and Pannwitz [HoPa34] proved $f_2(n)=n$ (with an elegant simple proof described by Erdős in [Er46b]).


• Grünbaum [Gr56], Heppes [He56], and Strasziewicz [St57] independently showed that $f_3(n)=2n-2$.


• Erdős [Er60b] proved that, for $d\geq 4$, $f_d(n)=(\frac{p-1}{2p}+o(1))n^2$ where $p=\lfloor d/2\rfloor$.


• Swanepoel [Sw09] gave, for all $d\geq 4$, an exact description of $f_d(n)$ for all $n$ sufficiently large depending on $d$, and also gave the extremal configurations.

See also [132], and [1084] for the analogous problem with minimal distance $1$.

View the LaTeX source

This page was last edited 28 October 2025.

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

View the LaTeX source

This page was last edited 28 October 2025.

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 discs of radius $1/2$ at a regular hexagonal lattice suitably spaced apart. 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$.

View the LaTeX source

This page was last edited 02 October 2025.

Erdős (unpublished) proved that this is true if $A$ has infinite measure, or if $A$ is an unbounded set of positive measure (stating in [Er78d] and [Er83d] it 'follows easily from the Lebesgue density theorem').

In [Er78d] and [Er83d] he speculated that perhaps $C=4\pi/\sqrt{27}\approx 2.418$ works, which would be the best possible, as witnessed by a circle of radius $<2\cdot 3^{-3/4}$.

Further evidence for this is given by a result of Freiling and Mauldin [Ma02], who proved that if $A$ has outer measure $>4\pi/\sqrt{27}$ then $A$ contains the vertices of a triangle with area $>1$. This also proves the same threshold for the original problem under the assumption that $A$ is a compact convex set.

Mauldin also discusses this problem in [Ma13], in which he notes that it suffices to prove this under the assumption that $A$ is the union of the interiors of $n<\infty$ many compact convex sets. Freiling and Mauldin (see [Ma13]) have proved this conjecture if $1\leq n\leq 3$.

View the LaTeX source

This page was last edited 27 December 2025.

Erdős and Mauldin (unpublished) claim that this is true for trapezoids in general, but fails for parallelograms (a construction showing this fails for parallelograms was provided by Kovač) [Ko23].

Kovač and Predojević [KoPr24] have proved that this is true for cyclic quadrilaterals - that is, every set with infinite measure contains four distinct points on a circle such that the quadrilateral determined by these four points has area $1$. They also prove that there exists a set of infinite measure such that every convex polygon with congruent sides and all vertices in the set has area $<1$.

Koizumi [Ko25] has resolved this question, proving that any set with infinite measure must contain the vertices of an isosceles trapezoid, an isosceles triangle, and a right-angled triangle, all of area $1$.

View the LaTeX source

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$. In fact, since these points are on a hyperplane, a suitable projection gives an improved lower bound of $\binom{n+1}{2}$ (see the construction of Alweiss given in [503]).

View the LaTeX source

When $d=2$ the answer is $6$ (due to Kelly [ErKe47] - an alternative proof is given by Kovács [Ko24c]). When $d=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{d+2}{2}.\]Alweiss has observed a lower bound of $\binom{d+1}{2}$ follows from considering the subset of $\mathbb{R}^{d+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}^d$, and is easily checked to have the required property.

Weisenberg observed in the comments that an additional point can be added to Alweiss' construction, giving a lower bound of $\binom{d+1}{2}+1$.

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

See also [1088] for a generalisation.

View the LaTeX source

This page was last edited 28 October 2025.

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

View the LaTeX source

This page was last edited 16 October 2025.

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

In [Er81b] Erdős wrote 'I suspect that it is false for sufficiently high dimensions'.

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

View the LaTeX source

This page was last edited 30 December 2025.

There is clearly some non-degeneracy condition intended here - probably either that not all the points are on a line, or the stronger condition that no three points are on a line.

This was resolved by Elliott [El67], who proved that (assuming not all points are on a circle or a line), provided $n>393$, the points determine at least $\binom{n-1}{2}$ distinct circles.

The problem appears to remain open for small $n$. Segre observed that projecting a cube onto a plane shows that the lower bound $\binom{n-1}{2}$ is false for $n=8$.

See also [104] and [831].

View the LaTeX source

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^{7/6+o(1)}}.\]The lower bound is due to Komlós, Pintz, and Szemerédi [KPS82]. The upper bound is due to Cohen, Pohoata, and Zakharov [CPZ24] (improving on their earlier work [CPZ23] which itself improves an exponent of $8/7$ due to Komlós, Pintz, and Szemerédi [KPS81]).

This problem is Problem 77 on Green's open problems list.

View the LaTeX source

This page was last edited 30 December 2025.

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

See also [704], [705], and [706]. The independence number of a finite unit distance graph is the topic of [1070].

View the LaTeX source

This page was last edited 16 October 2025.

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ős (unpublished) improved to $a_n=\frac{1}{n}$. Erdő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.\]

View the LaTeX source

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$. Jacobsen, Scullard, and Guttmann [JSG16] have computed the first few decimal places of $C_2$, showing that\[C_2 = 2.6381585303279\cdots.\]See also [529].

View the LaTeX source

Slade [Sl87] proved that, for $k$ sufficiently large, $d_k(n)\sim Dn^{1/2}$ for some constant $D>0$ (independent of $k$). Hara and Slade ([HaSl91] and [HaSl92]) proved this for all $k\geq 5$.

For $k=2$ Duminil-Copin and Hammond [DuHa13] have proved that $d_2(n)=o(n)$.

It is now conjectured that $d_k(n)\ll n^{1/2}$ is false for $k=3$ and $k=4$, and more precisely (see for example Section 1.4 of [MaSl93]) that $d_2(n)\sim Dn^{3/4}$, $d_3(n)\sim n^{\nu}$ where $\nu\approx 0.59$, and $d_4(n)\sim D(\log n)^{1/8}n^{1/2}$.

Madras and Slade [MaSl93] have a monograph on the topic of self-avoiding walks.

See also [528].

View the LaTeX source

This page was last edited 27 December 2025.

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 [Ka63] proved\[f_k(n)\gg_k n\log n\](resolving a conjecture of Erdős that $f_k(n)/n\to \infty$). 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})}\]

View the LaTeX source

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

Füeredi [Fu91b] proved\[n^{1/2}\log n\ll g(n)=o(n).\]Balogh and Solymosi [BaSo18] improved the upper bound to\[g(n) \ll n^{5/6+o(1)}.\]

View the LaTeX source

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 - for example, if $d(x)$ counts the number of distinct distances from $x$ then in [Er75f] Erdős conjectured\[\sum_{x\in A}d(x) \gg \frac{n^2}{\sqrt{\log n}},\]where $A\subset \mathbb{R}^2$ is any set of $n$ points.

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

View the LaTeX source

This page was last edited 15 October 2025.

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

View the LaTeX source

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.

View the LaTeX source

Erdős writes it is 'easy to see' that this bound would be best possible. This was proved by Szemerédi and Trotter [SzTr83].

View the LaTeX source

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

View the LaTeX source

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

Zhang [Zh25], among other results, has proved that for any integers $a \geq b$, if\[n\geq 3\left\lceil \frac{a^2+b^2+ab-a-b}{ab}\right\rceil\]then $n^2ab$ has this property (indeed, they explicitly show that an equilateral triangle can be tiled with $n^2ab$ many triangles of side lengths $a,b,\sqrt{a^2+b^2+2+ab}$).

See also [633].

View the LaTeX source

This page was last edited 30 December 2025.

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

View the LaTeX source

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

View the LaTeX source

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

View the LaTeX source

It is clear that every point has at least $\frac{n-1}{3}$ distinct distances to other points in the set.

In [Er87b] and [ErPa90] Erdős and Pach ask this under the additional assumption that there are no three points on a line (so that the points are in general position), although they only ask the weaker question whether there is a lower bound of the shape $(\tfrac{1}{3}+c)n$ for some constant $c>0$.

They suggest the lower bound $(1-o(1))n$ is true under the assumption that any circle around a point $x_i$ contains at most $2$ other $x_j$.

View the LaTeX source

This page was last edited 02 October 2025.

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.

Zach Hunter has observed that taking $n$ points equally spaced on a circle disproves this conjecture. In the spirit of related conjectures of Erdős and others, presumably some kind of assumption that the points are in general position (e.g. no three on a line and no four on a circle) was intended.

View the LaTeX source

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$. Sarosh Adenwalla has observed that this is equivalent to minimising the number of distinct differences in a set $A\subset \mathbb{R}$ of size $n$ without three-term arithmetic progressions. Dumitrescu [Du08] proved that, in these terms,\[(\log n)^c \leq f(n) \leq 2^{O(\sqrt{\log n})}\]for some constant $c>0$.

Hunter observed in the comments that a result of Ruzsa coupled with standard tools of additive combinatorics (with details given by Alfaiz and Tang) allow recent progress on the size of subsets without three-term arithmetic progression (see [BlSi23] which improves slightly on the bounds due to Kelley and Meka [KeMe23]) yield\[2^{c(\log n)^{1/9}}\leq f(n)\]for some constant $c>0$.

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

View the LaTeX source

This page was last edited 15 October 2025.

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

There does exist such a set: a suitable truncation of the lattice $\{(a,b\sqrt{2}): a,b\in\mathbb{Z}\}$ suffices. This construction appears to have been first considered by Moree and Osburn [MoOs06], who proved that it has $\ll \frac{n}{\sqrt{\log n}}$ many distinct distances. This construction was independently found by Lund and Sheffer, who further noted that this configuration contains no squares or equilateral triangles.

There are only six possible configurations of $4$ points which determine only $2$ distances (first noted by Erdős and Fishburn [ErFi96]), and five of them contain either a square or an equilateral triangle. The remaining configuration contains four points from a regular pentagon, and Grayzel (using Gemini) has noted in the comments that this configuration can also be ruled out, thus giving a complete solution to this problem.

See also [135].

View the LaTeX source

This page was last edited 16 January 2026.

For the similar problem in $\mathbb{R}^2$ there are always at least $n/2$ distances, as proved by Altman [Al63] (see [93]). In [Er75f] Erdős claims that Altman proved that the vertices determine $\gg n$ many distinct distances, but gives no reference.

View the LaTeX source

This page was last edited 01 January 2026.

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 =o(f)$?

See also [89].

View the LaTeX source

This page was last edited 11 January 2026.

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.

View the LaTeX source

In fact this is $=1$ also for $n=4$, the unique example given by two equilateral triangles joined by an edge.

Computational evidence of Engel, Hammond-Lee, Su, Varga, and Zsámboki [EHSVZ25] and Alexeev, Mixon, and Parshall [AMP25] suggests that this count is $=1$ for various other $5\leq n\leq 21$ (although these calculations were checking only up to graph isomorphism, rather than congruency).

The actual maximal number of unit distances is the subject of [90].

View the LaTeX source

This page was last edited 27 December 2025.

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)}.\]See also [101].

View the LaTeX source

This page was last edited 27 December 2025.

The lower bound of $\binom{n}{2}$ for the diameter is trivial. Erdős [Er97f] proved the claim when $d=1$.

View the LaTeX source

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.


See also [508], [705], and [706].

View the LaTeX source

This problem is essentially the same as [607], but with multiplicities.

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 expected proving the upper bound to be difficult. Once it is done, he asked 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.

This is true, and was proved by Szemerédi and Trotter [SzTr83].

See also [732].

View the LaTeX source

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

View the LaTeX source

Avis, Erdős, and Pach [AEP88] proved that\[\frac{n}{2}+2 \leq f(n) \leq (1+o(1))\frac{n}{2}.\]This was proved by Swanepoel [Sw13], who in fact proved more generally that, in any finite set $A\subset \mathbb{R}^4$ of size $n$ and any choice of distance $d(x)$ for each $x\in A$,\[\sum_{x\in A}\sum_{y\in A}1_{\lvert x-y\rvert =d(x)}\leq \tfrac{1}{2}n^2+O(n),\]and proved similar results for finite point sets in higher dimensional space.

View the LaTeX source

Let $T_6^u(n)$ count the maximal number of equilateral triangles of size $1$ formed by $n$ points in $\mathbb{R}^6$. The following construction (which [Er94b] attributes to Lenz, but appears in an earlier paper of Erdős and Purdy [ErPu75]) shows that\[T_6^u(n)\geq \frac{n^3}{27}-O(n^2):\]take three suitable orthogonal circles and take $n/3$ points on each of them which form $n/4$ inscribed squares.

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

This problem was solved in a strong form by Clemen, Dumitrescu, and Liu [CDL25b], who in fact prove that if $T_6(n)$ is the maximal number of equilateral triangles of any size formed by $n$ points in $\mathbb{R}^6$ then\[T_6(n)=(\tfrac{1}{27}+o(1))n^3.\]Indeed, they give an exact formula for $T_d(n)$ for all even $d\geq 6$ (and sufficiently large $n$).

See also [1086].

View the LaTeX source

This page was last edited 16 October 2025.

Asked by Erdős and Pach in the stronger form of whether all distances (aside from the largest) can occur with multiplicity $>n$. 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.

Further investigations were undertaken by Clemen, Dumitrescu, and Liu [CDL25], who proved, amongst other results, that if we take $A$ to be the square grid of $n$ points, then there are at least $n^{c/\log\log n}$ many distances which occur with multiplicity at least $n^{1+c/\log\log n}$ (for some constant $c>0$).

See also [132] and [957].

View the LaTeX source

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.

Without loss of generality, one can assume $A\subset \mathbb{N}$.

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

View the LaTeX source

This page was last edited 08 January 2026.

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

Hudelson [Hu98] proved that if $(2^n-1,3^n-1)=1$ then $c(n) < 6^n$, and in general $c(n) \ll (2n)^{n-1}$. Connor and Marmorino [CoMa18] proved that\[c(n) \geq 2^{n+1}-1\]for all $n\geq 3$,\[c(n) \leq 1.8n^{n+1}\]if $n+1$ is prime, and\[c(n) \leq e^2n^n\]otherwise.

View the LaTeX source

This page was last edited 01 October 2025.

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

View the LaTeX source

In [Er75h] Erdős asks whether $n_k$ exists. In [Er78c] he gave a simple argument which proves that it does, and in fact\[n_k \leq k+2\binom{k-1}{2}\binom{k-1}{3},\]but this argument is incorrect, as explained by Martinez and Roldán-Pensado [MaRo15].

Martinez and Roldán-Pensado give a corrected argument that proves $n_k\ll k^9$.

View the LaTeX source

This page was last edited 24 October 2025.

See also [104] and [506].

View the LaTeX source

A question of Erdős and Hammer. Erdős proved in [Er78c] that there exist constants $c_1,c_2>0$ such that\[n^{c_1\log n}<f(n)< n^{c_2\log n}.\]See also [107].

View the LaTeX source

A problem of Erdős, Nešetřil, and Rödl.

See also [774] and [847].

View the LaTeX source

Conjectured by Erdős in 1932 (according to [Er82e]) and proved by Mordell soon afterwards, now known as the Erdős-Mordell inequality.

View the LaTeX source

This page was last edited 16 November 2025.

A problem of Erdős and Sárközi. Erdős [Er77c] writes that 'Sárközi has the sharpest results, but nothing has been published yet'.

The trivial upper bound is $O(r)$. Kovac has observed that Sárközy's lower bound in [466] can be adapted to give a lower bound of $\gg r^{0.26}$ for this problem.

See also [465] for a similar problem (concerning upper bounds) and [466] for a similar problem (concerning lower bounds).

View the LaTeX source

This page was last edited 16 September 2025.

A problem of Erdős and Pach [ErPa90], who proved that $h(n) \ll n^{4/3}$. They also consider the related function where we consider $n$ disjoint convex sets (not necessarily translates), for which they give an upper bound of $\ll n^{7/5}$.

It is trivial that $h(n)\geq f(n)$, where $f(n)$ is the maximal number of unit distances determined by $n$ points in $\mathbb{R}^2$ (see [90]).

View the LaTeX source

A question of Erdős and Pach [ErPa90], who write that an 'easy' unpublished construction of Makai shows that this would be the best possible, and that it is 'not difficult' to prove\[f(d_1)+f(d_k) \leq 3n -c\sqrt{n}+o(\sqrt{n})\]for some $c>0$, and ask what the best possible value of $c$ is.

A stronger version of this problem (which implies the inequality in the problem statement) is that\[f(d_1)\leq 3n-2m+o(\sqrt{n}),\]where $m$ is the number of vertices of the convex hull of $A$.

The odd regular polygon shows that it is possible for $f(d_i)\geq n$ for all $i$.

The original problem was solved by Dumitrescu [Du19], who proved that\[f(d_1)f(d_k)\leq \frac{9}{8}n^2+O(n).\]See also [132] and [756].

View the LaTeX source

Erdős conjectured that the answer is no, and other such configurations exist.

This was proved by Clemen, Dumitrescu, and Liu [CDL25], who observed that equidistant points on a short circular arc on a circle of radius $1$, together with the centre, are also an example.

View the LaTeX source

More generally, one can ask about\[\max (f(d_r)-f(d_{r+1})).\]Clemen, Dumitrescu, and Liu [CDL25], have shown that\[\max (f(d_1)-f(d_2))\gg n\log n.\]More generally, for any $1\leq k\leq \log n$, there exists a set $A$ of $n$ points such that\[f(d_r)-f(d_{r+1})\gg \frac{n\log n}{r}.\]They conjecture that $n\log n$ can be improved to $n^{1+c/\log\log n}$ for some constant $c>0$.

View the LaTeX source

Turán's theorem implies\[f_{r,k}(n) \leq \left(1-\frac{1}{r-1}\right)\frac{n^2}{2}+1.\]See also [209].

View the LaTeX source

The regular polygon shows that $\lfloor n/2\rfloor$ is the best possible here.

This would be implied if there was a vertex such that no three vertices of the polygon are equally distant to it, which was originally also conjectured by Erdős [Er46b], but this is false (see [97]).

Let $f(n)$ be the maximal number of such distances that are guaranteed. Moser [Mo52] proved that\[f(n) \geq \left\lceil\frac{n}{3}\right\rceil.\]This was improved by Erdős and Fishburn [ErFi94] to\[f(n) \geq \left\lfloor \frac{n}{3}+1\right\rfloor,\]then\[f(n) \geq \left\lceil \frac{13n-6}{36}\right\rceil\]by Dumitrescu [Du06b], and most recently\[f(n) \geq \left(\frac{13}{36}+\frac{1}{22701}\right)n-O(1)\]by Nivasch, Pach, Pinchasi, and Zerbib [NPPZ13].

In [Er46b] Erdős makes the even stronger conjecture that on every convex curve there exists a point $p$ such that every circle with centre $p$ intersects the curve in at most $2$ points. Bárány and Roldán-Pensado [BaRo13] noted that the boundary of any acute triangle is a counterexample.

Bárány and Roldán-Pensado prove that, for any planar convex body, there is a point $p$ on the boundary such that every circle with centre $p$ intersects the boundary in at most $O(1)$ (where the implied constant depends on the convex body). They conjecture that there this can be bounded by an absolute constant - that is, Erdős's conjecture is true if we replace $2$ by some larger constant $C$.

See also [93].

View the LaTeX source

This page was last edited 19 October 2025.

In [Er87b] Erdős describes this as a conjecture of himself, Croft, and Purdy.

This is true, and was proved by Szemerédi and Trotter [SzTr83].

The best possible value of the implied constant is unknown. When $k=n^{1/2}$ the lattice points show that there can be $\geq(2+o(1))n^{1/2}$ many $n^{1/2}$-rich lines. Erdős thought that perhaps this is best possible, but Sah [Sa87] gave a construction achieving $\geq (3+o(1))n^{1/2}$ many $n^{1/2}$-rich lines.

View the LaTeX source

This page was last edited 02 October 2025.

In other words, estimate the minimal independence number of a unit distance graph with $n$ vertices. If $\omega$ is the independence number and $\chi$ is the chromatic number then $\omega \chi\geq n$, and hence $f(n)\geq n/\chi$, where $\chi$ is the answer to the Hadwiger-Nelson problem [508].

The Moser spindle shows $f(n)\leq \frac{2}{7}n\approx 0.285n$. Larman and Rogers [LaRo72] noted that if $m_1$ is the supremum of the upper densities of measurable subsets of $\mathbb{R}^2$ which have no unit distance pairs then\[f(n)\geq m_1n.\]Croft [Cr67] gave the best-known lower bound of $m_1\geq 0.22936$ and hence\[0.22936n \leq f(n) \leq \frac{2}{7}n\approx 0.285n.\]Ambrus, Csiszárik, Matolcsi, Varga, and Zsámboki [ACMVZ23] have proved that $m_1\leq 0.247$, and hence this approach cannot achieve $f(n)\geq n/4$. See [232] for more on $m_1$.

If we also insist that no two points are distance $<1$ apart then this is problem becomes [1066].

View the LaTeX source

This page was last edited 02 October 2025.

A question of Erdős and Tóth. The answer to the first question is yes (which Erdős gave Danzer \$10 for). There is no prize mentioned in [Er87b] for the (still open) second question.

There are two examples Erdős gives in [Er87b], the first by Danzer, the second by an unnamed participant.

In [Er87b] he further asks what happens if the unit line segments are rotated/translated copies of $[0,1]$ that are allowed to intersect only at their endpoints.

View the LaTeX source

This page was last edited 16 January 2026.

A conjecture of Szemerédi, who proved this with $n/2$ replaced by $n/3$. More generally, Szemerédi gave a simple proof that if there are no $k$ points on a line then some point determines $\gg n/k$ distinct distances (a weak inverse result to the distinct distance problem [89]).

This is a stronger form of [93]. The second question is a stronger form of [982].

Szemerédi's proof is unpublished, but given in [Er75f].

In [Er75f] Erdős asks whether, given $n$ points in $\mathbb{R}^3$ with no three on a line, do they determine $\gg n$ distances? Altman proved the answer is yes if the points form the vertices of a convex polyhedron (see [660] for a stronger form of this), and Szemerédi proved the answer is yes if there are no four points on a plane.

The stronger second question has been answered negatively by Xichuan in the comments, who gave a set of $42$ points in $\mathbb{R}^2$, with no three on a line, such that each point determines only $20$ distinct distances.

View the LaTeX source

This page was last edited 20 December 2025.

A generalisation of the distinct distance problem [89] to higher dimensions. Erdős [Er46b] proved\[n^{1/d}\ll_d f_d(n)\ll_d n^{2/d},\]the upper bound construction being given by a set of lattice points.

• Clarkson, Edelsbrunner, Gubias, Sharir, and Welzl [CEGSW90] proved $f_3(n)\gg n^{1/2}$.


• Aronov, Pach, Sharir, and Tardos [APST04] proved $f_d(n)\gg n^{\frac{1}{d-90/77}-o(1)}$ for any $d\geq 3$ (for example, $f_3(n)\gg n^{0.546}$).


• Solymosi and Vu [SoVu08] proved $f_3(n) \gg n^{3/5}$ and\[ f_d(n)\gg_d n^{\frac{2}{d}-\frac{c}{d^2}}\]for all $d\geq 4$ for some constant $c>0$. (The result in their paper for $d=3$ is slightly weaker than stated here, but uses as a black box the bound for distinct distances in $2$ dimensions; we have recorded the consequence of combining their method with the work of Guth and Katz on [89].)

The function $f_d(n)$ is essentially the inverse of the function $g_d(n)$ considered in [1089] - with our definitions, $g_d(n)>m$ if and only if $f_d(m)<n$. The emphasis in this problem is, however, on the behaviour as $d$ is fixed and $n\to \infty$.

View the LaTeX source

This page was last edited 16 October 2025.

It is easy to see that $f_1(n)=n-1$ and $f_2(n)<3n$ (since there can be at most $6$ points of distance $1$ from any point). Erdős [Er46b] showed\[f_2(n)<3n-cn^{1/2}\]for some constant $c>0$, which the triangular lattice shows is the best possible up to the value of $c$. In [Er75f] he speculated that the triangular lattice is exactly the best possible, and in particular\[f_2(3n^2+3n+1)=9n^2+6n.\]In [Er75f] he claims the existence of $c_1,c_2>0$ such that\[6n-c_1n^{2/3}< f_3(n) < 6n-c_2n^{2/3}.\]See [223] for the analogous problem with maximal distance $1$.

View the LaTeX source

This page was last edited 15 October 2025.

The most difficult cases are $d=2$ and $d=3$. When $d=2$ this is the unit distance problem [90], and the best known bounds are\[n^{1+\frac{c}{\log\log n}}< f_2(n) \ll n^{4/3}\]for some constant $c>0$, the lower bound by Erdős [Er46b] and the upper bound by Spencer, Szemerédi, and Trotter [SST84].

When $d=3$ the best known bounds are\[n^{4/3}\log\log n \ll f_3(n) \ll n^{3/2}\beta(n)\]where $\beta(n)$ is a very slowly growing function, the lower bound by Erdős [Er60b] and the upper bound by Clarkson, Edelsbrunner, Guibas, Sharir, and Welzl [CEGSW90].

A construction of Lenz (taking points on orthogonal circles) shows that, for $d\geq 4$,\[f_d(n)\geq \frac{p-1}{2p}n^2-O(1)\]with $p=\lfloor d/2\rfloor$. Erdős [Er60b] showed that the Erdős-Stone theorem implies\[f_d(n) \leq \left(\frac{p-1}{2p}+o(1)\right)n^2\]for $d\geq 4$.

Erdős [Er67e] determined $f_d(n)$ up to $O(1)$ for all even $d\geq 4$. Brass [Br97] determined $f_4(n)$ exactly. Swanepoel [Sw09] determined $f_d(n)$ exactly for even $d\geq 6$. For odd $d\geq 5$ Erdős and Pach [ErPa90] proved that there exist constants $c_1(d),c_2(d)>0$ such that\[\frac{p-1}{2p}n^2 +c_1n^{4/3}\leq f_d(n) \leq \frac{p-1}{2p}n^2 +c_2n^{4/3}.\]

View the LaTeX source

This page was last edited 17 October 2025.

Equivalently, how many triangles of area $1$ can a set of $n$ points in $\mathbb{R}^2$ determine? Erdős and Purdy attribute this question to Oppenheim. Erdős and Purdy [ErPu71] proved\[n^2\log\log n \ll g(n) \ll n^{5/2},\]and believed the lower bound to be closer to the truth. The upper bound has been improved a number of times - by Pach and Sharir [PaSh92], Dumitrescu, Sharir, and Tóth [DST09], Apfelbaum and Sharir [ApSh10], and Apfaulbaum [Ap13]. The best known bound is\[g(n) \ll n^{20/9}\]by Raz and Sharir [RaSh17].

Erdős and Purdy also ask a similar question about the higher-dimensional generalisations - more generally, let $g_d^{r}(n)$ be minimal such that any set of $n$ points in $\mathbb{R}^d$ contains the vertices of at most $g_d^{r}(n)$ many $r$-dimensional simplices with the same volume.

Erdős and Purdy [ErPu71] proved $g_3^2(n) \ll n^{8/3}$, and Dumitrescu, Sharir, and Tóth [DST09] improved this to $g_3^2(n) \ll n^{2.4286}$.
Erdős and Purdy [ErPu71] proved $g_6^2(n)\gg n^3$. Purdy [Pu74] proved\[g_4^2(n)\leq g^2_5(n) \ll n^{3-c}\]for some constant $c>0$. An observation of Oppenheim (using a construction of Lenz) detailed in [ErPu71] shows that\[g_{2k+2}^k(n)\geq \left(\frac{1}{(k+1)^{k+1}}+o(1)\right)n^{k+1}\]and Erdős and Purdy conjecture this is the best possible.

See also [90] and [755].

View the LaTeX source

This page was last edited 16 October 2025.

A question of Erdős and Purdy [ErPu71], who proved\[n^3\log n \ll f(n) \ll n^{7/2}.\]

View the LaTeX source

It is easy to prove that $f_d(n) \leq n^{O_d(1)}$. Erdős [Er75f] claimed that he and Straus proved $f_d(n)\leq c_n^d$ for some constant $c_n>0$.

When $d=1$ this is the subject of [530], and $f_1(n)\asymp n^2$.

When $n=3$ this is the subject of [503]. Erdős could prove $f_2(3)=7$ and Croft [Cr62] proved $f_3(3)=9$. The results described at [503] demonstrate that $f_d(3)=d^2/2+O(d)$.

View the LaTeX source

This page was last edited 16 October 2025.

A question of Kelly. Erdős [Er75f] writes it is 'easy' to see that $g_d(n)\gg d^{n-1}$. Erdős and Straus proved (in unpublished work mentioned in [Er75f]) that\[g_d(n) \leq c^{d^{1-b_n}}\]for some constants $c>0$ and $b_n>0$.

It is trivial that $g_1(3)=4$, and easy to see that $g_2(3)=6$. Croft [Cr62] proved $g_3(3)=7$. The vertices of a $d$-dimensional cube demonstrate that\[g_d(d+1)>2^d.\]The function $g_d(n)$ is essentially the inverse of the function $f_d(n)$ considered in [1083] - with our definitions, $g_d(n)>m$ if and only if $f_d(m)<n$. The emphasis in this problem is, however, on the behaviour for fixed $n$ as $d\to\infty$.

View the LaTeX source

This page was last edited 16 October 2025.

Erdős [Er75f] says Graham and Selfridge proved the answer is yes when $k=3$.

Hunter has observed that, for sufficiently large $n$, a generic projection of $[k]^n$ into $\mathbb{R}^2$ has this property, by the Hales-Jewett theorem.

View the LaTeX source

This page was last edited 19 October 2025.

This was reported as a conjecture of Erdős in [GoGo45].

This is true, and was proved by Goodman and Goodman [GoGo45] (whose proof also generalises to higher dimensions).

View the LaTeX source

This page was last edited 30 December 2025.

A problem of Tarski, which Erdős described as 'a very beautiful problem...if it were my problem I would offer \$1000 for it'.

This is true - Laczkovich [La90b] proved that in fact this is possible using translations only.

View the LaTeX source

This is true (assuming the continuum hypothesis) when $n=1$, since Erdős and Kakutani [ErKa43] proved that in fact the continuum hypothesis is equivalent to the statemant that $\mathbb{R}$ can be written as the union of countably many sets, each of which is linearly independent over $\mathbb{Q}$.

Davies [Da72] proved this true when $n=2$, and Kunen [Ku87] proved it is true for all $n$ (again, both assuming the continuum hypothesis).

The dependence on the continuum hypothesis is necessary, since Erdős and Hajnal proved that if the continuum hypothesis is false then e.g. in any decomposition of $\mathbb{R}$ into finitely many sets there exist four points which determine only four distances.

View the LaTeX source

This page was last edited 30 December 2025.