CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Algorithms, Combinatorics and Optimization Seminar

For more information, please visit the home page for the program in Algorithms, Combinatorics and Optimization at Carnegie Mellon University.

Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics and Optimization. This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group) and the Department of Mathematical Sciences (Discrete Mathematics group). (Learn more...)


Adam Sheffer
Tel Aviv University
Title: Recent progress in distinct distances problems

Abstract: During 2013, significant progress has been obtained for several problems that are related to the Erdős distinct distances problem. In this talk I plan to briefly describe some of these results and the tools that they rely on. I will focus on the following two results.

Let P and P' be two sets of points in the plane, so that P is contained in a line L, P' is contained in a line L', and L and L' are neither parallel nor orthogonal. Then the number of distinct distances determined by the pairs of PP' is Ω(min{|P|2/3|P'|2/3,|P|2, |P'|2}). In particular, if |P|=|P'|=m, then the number of these distinct distances is Ω(m4/3), improving upon the previous bound Ω(m5/4) of Elekes.

In the second result, we study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set P of n points determines o(n) distinct distances, then no line contains Ω(n7/8) points of P and no circle contains Ω(n5/6) points of P.

In both cases, we rely on a bipartite and partial variant of the Elekes‒Sharir framework, which has been used by Guth and Katz in their 2010 solution of the general distinct distances problem. We combine this framework with some basic algebraic geometry, with a theorem from additive combinatorics by Elekes, Nathanson, and Ruzsa, and with a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang.

The first result is a joint work Micha Sharir (Tel Aviv) and József Solymosi (UBC). The second is a joint work with Joshua Zahl (MIT) and Frank de Zeeuw (EPFL).

Date: Thursday, December 5, 2013
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Boris Bukh