Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Unit and distinct distances in typical norms 

Matija Bucic (Princeton/IAS)

Location:  Hill Center Room 705
Date & time: Monday, 13 February 2023 at 2:00PM - 3:00PM

Abstract: Erd?s' unit distance problem and Erd?s' distinct distances problem are among the most classical and well-known open problems in all of discrete mathematics. They ask for the maximum number of unit distances, or the minimum number of distinct distances, respectively, determined by n points in the Euclidean plane. The question of what happens in these problems if one considers normed spaces other than Euclidean space has been raised in the 1980s by Ulam and Erd?s and attracted a lot of attention over the years. We give an essentially tight answer to both questions for almost all norms on R^d, in a certain Baire categoric sense.

Our results settle, in a strong and somewhat surprising form, problems and conjectures of Brass, of Matousek, and of Brass--Moser--Pach. The proofs combine combinatorial, probabilistic and geometric ideas with tools from Linear Algebra, Topology and Algebraic Geometry.

Joint work with: Noga Alon and Lisa Sauermann.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.