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.

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

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

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.

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

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.