MIF Series
2026-03-17 13:00 - 14:00
Janos Pach: On the distribution of distances: Quo vadis?

In 1946, Paul Erd?s raised two different problems for the distribution of distances among n points in the plane: (1) What is the minimum number of distinct distances determined by n points in R2? (2) What is the maximum number of times the same distance can occur among n points in R2? The first problem was almost solved by Guth and Katz in 2015 (up to a logarithmic factor). Regarding the second problem, Spencer, Szemerédi, and Trotter proved in 1983 that the maximum is O(n4/3). Over the past 40 years, several new proofs have been found for this bound, but no improvement has been made. After giving a whirlwind survey of the known results and their applications in number theory and computer science, we describe an approach to the second problem, based on graph rigidity. Joint work with O. Raz and J. Solymosi.

https://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1484
