# Combinatorics Seminar

When: Sunday, May 15, 10am

Where: Schreiber 309

Speaker: Noam Solomon, Tel Aviv U.

Title: Distinct and repeated distances on a surface in R^3

## Abstract:

In their seminal paper from 2010, Guth and Katz proved
that the number of distinct distances determined by a set of n
points in \mathbb R^2 is \Omega(n/\log n), thus (almost) settling
Erd{\H o}s's distinct distances problem, open for nearly 65 years. In
\mathbb R^3, it is conjectured that a set of n points determines at
least \Omega(n^{2/3}) distinct distances. This bound is best possible
as it is attained by the vertices of the n^{1/3} \times n^{1/3}
\times n^{1/3} integer grid. This problem however is still wide open,
for many years. The best known lower bound is due to Solymosi and Vu.

In a recent work with Micha Sharir, we showed that the number of
distinct distances determined by a set of n points on a
constant-degree algebraic surface in \mathbb R^3 is at least
\Omega\left(n^{7/9}/\polylog \,n\right).
This bound is significantly larger than the conjectured bound
\Omega(n^{2/3}) for general point sets in \mathbb R^3.

We also showed that the number of unit distances determined by n
points on a surface V, as above, is O(n^{4/3}), a bound that
matches the best known planar bound, and is worst-case tight in
3-space.
This is in sharp contrast with the best known general bound
O(n^{3/2})
for points in three dimensions.

In this talk, I will present these recent results, along with the
relevant background. No prior knowledge is assumed.

redesigned by barak soreq