Videos

Erd\H{o}s Unit Distance Problem and Graph Rigidity

Presenter
March 10, 2025
Abstract
Erd\H{o}s unit distance problem asks the following: Let Pbe a set of n distinct points in the plane, and let U(P)denote the number of pairs of points in P that are at distance 1. How large can U(P) be? In 1946, Erd\H{o}s showed that for P=[n‾√]×[n‾√], one has U(P)=Θ(n1+cloglogn), for some constant c greater than 0, and he conjectured that this is best possible. While the problem has received a lot of attention, the best upper bound, established by Spencer, Szemer\'edi, and Trotter in 1984, is U(P)=O(n4/3), with no progress in the last 40 years. One reason for the difficulty of the problem is that the current combinatorial geometry tools, dealing with properties of unit circles, actually apply to more general families of curves. For the latter families, the upper bound of O(n4/3) is, in fact, tight.In the talk, I will introduce a completely new approach to the unit distance problem, relating the problem to a question in graph rigidity theory. Specifically, I will present a new structure theorem, that applies to point configurations with many unit distances, and pose a new conjecture regarding rigid subgraphs. I will then explain how a solution of the rigidity conjecture, would, for the first time, yield an improvement of the aforementioned upper bound for the unit distance problem. If time permits, I will explain how to prove a weaker version of the rigidity conjecture, by reducing the problem to a line-line incidence question in ℝ3.The talk is based on a joint work with J. Pach and J. Solymosi.