Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Wednesday, April 13, 2011, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Micha Sharir (Tel Aviv University)

From joints to distinct distances and beyond: The dawn of an algebraic era in combinatorial geometry II

In November 2010 the earth has shaken, when Larry Guth and Nets Hawk Katz posted a nearly complete solution to the distinct distances problem of Erd{\H o}s, open since 1946. The excitement was twofold: (a) The problem was one of the most famous problem, as well as one of the hardest nuts in the area, resisiting solution in spite of many attempts (which only produced partial improvements). (b) The proof techniques were algebraic in nature, drastically different from anything tried before.

The distinct distances problem is to show that any set of n points in the plane determine Omega(n/\sqrt{\log n}) distinct distances. (Erd{\H o}s showed that the grid attains this bound.) Guth and Katz obtained the lower bound Omega(n/\log n).

Algebraic techniques of this nature were introduced into combinatorial geometry in 2008, by the same pair Guth and Katz. At that time they gave a complete solution to another (less major) problem, the so-called joints problem, posed by myself and others back in 1992. Since then these techniques have led to several other developments, including an attempt, by Elekes and myself, to reduce the distinct distances problem to an incidence problem between points and lines in 3-space. Guth and Katz used this reduction and gave a complete solution to the reduced problem.

One of the old-new tools that Guth and Katz bring to bear is the Polynomial Ham Sandwich Cut, due to Stone and Tukey (1942). I will discuss this tool, including a ``1-line'' proof thereof, and its potential applications in geometry. One such application, just noted by Matou\v{s}ek, is an algebraic proof of the classical Szemer\'edi-Trotter incidence bound for points and lines in the plane.

In the talk I will review all these developments, as time will permit. Only very elementary background in algebra and geometry will be assumed.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login