The Erd\H{o}s unit distance problem and graph rigidity

The Erd\H{o}s unit distance problem asks the following: Let $P$ be 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=[\sqrt{n}]times [\sqrt{n}]$, one has $U(P)=Theta(n^{1+frac{c}{loglog n}})$, for some constant $c>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(n^{4/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(n^{4/3})$ is, in fact, tight.

In the talk, I will introduce a 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, which 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 $\mathbb{R}^3$.

The talk is based on a joint work with J. Pach and J. Solymosi.