Problem #96: If $n$ points in $\mathbb{R}^2$ form a convex polygon then...

---

Progress

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.