BEGIN:VCALENDAR VERSION:2.0 PRODID:-//jEvents 2.0 for Joomla//EN CALSCALE:GREGORIAN METHOD:PUBLISH BEGIN:VTIMEZONE TZID:America/New_York BEGIN:STANDARD DTSTART:20240127T140000 RDATE:20240310T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:STANDARD DTSTART:20241103T010000 RDATE:20250309T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:STANDARD DTSTART:20251102T010000 RDATE:20260308T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:STANDARD DTSTART:20261101T010000 RDATE:20270314T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:STANDARD DTSTART:20271107T010000 RDATE:20280312T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:STANDARD DTSTART:20281105T010000 RDATE:20290311T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:DAYLIGHT DTSTART:20240310T030000 RDATE:20241103T010000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:America/New_York EDT END:DAYLIGHT BEGIN:DAYLIGHT DTSTART:20250309T030000 RDATE:20251102T010000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:America/New_York EDT END:DAYLIGHT BEGIN:DAYLIGHT DTSTART:20260308T030000 RDATE:20261101T010000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:America/New_York EDT END:DAYLIGHT BEGIN:DAYLIGHT DTSTART:20270314T030000 RDATE:20271107T010000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:America/New_York EDT END:DAYLIGHT BEGIN:DAYLIGHT DTSTART:20280312T030000 RDATE:20281105T010000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:America/New_York EDT END:DAYLIGHT END:VTIMEZONE BEGIN:VEVENT UID:084d094eb4223f725bde8e629b70bcb1 CATEGORIES:Discrete Math CREATED:20250123T221730 SUMMARY:Orit Raz - Erdős unit distance problem and graph rigidity LOCATION:Hill 705 DESCRIPTION:Speaker: Orit Raz (https://www.ias.edu/scholars/orit-esther-raz) (IAS)\nTit le:  Erdős unit distance problem and graph rigidity\nAbstract: Erdős unit d istance 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$ t hat are at distance 1. How large can $U(P)$ be? In 1946, Erdő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 pos sible. While the problem has received a lot of attention, the best upper bo und, established by Spencer, Szemerédi, and Trotter in 1984, is $U(P)=O(n^{ 4/3})$, with no progress in the last 40 years. One reason for the difficult y 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 fa ct, tight. \n \nIn the talk, I will introduce a completely new approach to the unit distance problem, relating the problem to a question in graph rigi dity theory. Specifically, I will present a new structure theorem, that app lies to point configurations with many unit distances, and pose a new conje cture 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, b y reducing the problem to a line-line incidence question in $mathbb{R}^3$.\ n \nThe talk is based on a joint work with J. Pach and J. Solymosi. \n X-ALT-DESC;FMTTYPE=text/html:

Speaker: Orit Raz (IAS)

Title:  Erdős unit distance problem and graph rigidity

Abstract: E rdős unit distance problem asks the following: Let $P$ be a set of $n$ dist inct points in the plane, and let $U(P)$ denote the number of pairs of poin ts in $P$ that are at distance 1. How large can $U(P)$ be? In 1946, Erdős&n bsp; 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, t he best upper bound, established by Spencer, Szemerédi, and Trotter in 1984 , is $U(P)=O(n^{4/3})$, with no progress in the last 40 years. One reason f or the difficulty of the problem is that the current combinatorial geometry tools, dealing with properties of unit circles, actually apply to more gen eral 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 completely new approach to the unit distance problem, rel ating the problem to a question in graph rigidity theory. Specifically, I w ill present a new structure theorem, that applies to point configurations w ith many unit distances, and pose a new conjecture regarding rigid subgraph s. I will then explain how a solution of the rigidity conjecture, would, fo r the first time, yield an improvement of the aforementioned upper bound fo r 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 li ne-line incidence question in $mathbb{R}^3$.

 

Th e talk is based on a joint work with J. Pach and J. Solymosi. < /p> DTSTAMP:20260829T173954 DTSTART;TZID=America/New_York:20250127T140000 DTEND;TZID=America/New_York:20250127T150000 SEQUENCE:0 TRANSP:OPAQUE END:VEVENT END:VCALENDAR