Computer Science/Discrete Mathematics Seminar I
Unit and Distinct Distances in Typical Norms
Erdős' unit distance problem and his related distinct distances problem are arguably the best known open problems in discrete geometry.
They ask for the maximum possible number of unit distances, and the minimum possible number of distinct distances, respectively, determined by n points in the Euclidean plane. The same problems for normed spaces other than the Euclidean plane have been raised in the 1980s by Ulam and Erdős and attracted a lot of attention over the years. We give an essentially tight answer to both questions for almost all norms on $R^d$, in a certain Baire categoric sense.
The results settle, in a strong and somewhat surprising form, problems and conjectures of Brass, of Matousek, and of Brass-Moser-Pach. The proofs combine combinatorial and geometric ideas with tools from Linear Algebra, Topology and Algebraic Geometry.
Joint work with Matija Bucic and Lisa Sauermann.