Erdős Problems

FAQ Tags Prizes Definitions Links

3 solved out of 3 shown

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

#93: [Er57][Er90][Er95]

geometry, convex

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

#94: [Er95][Er97c]

geometry, convex

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

#95: [Er95][Er97c]

geometry, convex, distances

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