Nicole Nyberg: From graphs to polynomials: The unit distance problem in the plane

Abstract: The Erdos unit distance problem asks for the maximum number of unit distances determined by n points in the plane. The best known upper bound is \(O(n^{4/3})\). We examine the connection between the problem and graph theory. We give two different proofs of the Szemerédi--Trotter theorem, which bounds the number of incidences between points and lines in the plane, using both graph-theoretic and polynomial partitioning methods, and look at generalizations of this theorem. From this, the bound \(O(n^{4/3})\) follows. Furthermore, we study the number of unit distances for certain configurations and restrictions on our points. In addition, we describe a configuration that determines at least \(n^{1+c/\log{\log{n}}}\) unit distances, for some absolute constant c>0 and sufficiently large n. Furthermore, we introduce rigid frameworks for graphs and discuss a related conjecture, which, if it holds, yields an improvement on the upper bound \(O(n^{4/3})\) on the number of unit distances determined by n points in the plane.