BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Gábor Tardos (Alfréd Rényi Institute)
DTSTART:20200525T130000Z
DTEND:20200525T140000Z
DTSTAMP:20260404T163716Z
UID:EPC/7
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/EPC/7
 /">Planar point sets determine many pairwise crossing segments</a>\nby Gá
 bor Tardos (Alfréd Rényi Institute) as part of Extremal and probabilisti
 c combinatorics webinar\n\n\nAbstract\nWhat is the largest number $f(n)$ s
 uch that $n$ points in the plane (no three on a line) always determine $f(
 n)$ pairwise crossing segments. This natural question was asked by Aronov\
 , Erdős\, Goddard\, Kleitman\, Klugerman\, Pach\, and Schulman in 1991 a
 nd they proved $f(n)=\\Omega(\\sqrt{n})$. The prevailing conjecture was th
 at this bound is far from optimal and $f(n)$ is probably linear in $n$. Ne
 vertheless\, this lower bound was not improved till last year\, when  we p
 roved with János Pach and Natan Rubin an almost (but not quite) linear lo
 wer bound. Our result gives $f(n)>n/\\exp(O(\\sqrt{\\log n}))$. Determinin
 g whether $f(n)$ is truly linear is an intriguing open problem.\n\nPasswor
 d: the first 6 prime numbers (8 digits in total)\n
LOCATION:https://stable.researchseminars.org/talk/EPC/7/
END:VEVENT
END:VCALENDAR