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


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.

w3c valid   accessible website
redesigned by barak soreq