Universität Bonn

9th Colloquium of Research Area C3

Date:  June 21, 2024

Venue: Computer Science Building (Friedrich-Hirzebruch-Allee 8)

Research Area: C3 Combinatorial optimization, complexity, and chip design

Friday, June 21


Coffee and Tea (Room 2.075)


Lisa Sauermann: Unit distances and distinct distances in typical norms

Given n points in the plane, how many pairs among these points can have distance exactly 1? More formally, what is the maximum possible number of unit distances among a set of n points in the plane? This problem is a very famous and still largely open problem, called the Erdös unit distance problem. One can also study this problem for other norms on R2 (or more generally on Rd for any dimension d) that are different from the Euclidean norm. This direction has been suggested in the 1980s by Ulam and Erdös and attracted a lot of attention over the years. We give an almost tight answer to this question for almost all norms on Rd (for any given d). Furthermore, for almost all norms on Rd, we prove an asymptotically tight bound for a related problem, the so-called Erdös distinct distances problem. Joint work with Noga Alon and Matija Bucić.

Wird geladen