Discrete Math Seminar: Micha Sharir

  • Date: 09/15/2015
  • Time: 16:00
Lecturer(s):
Micha Sharir, Tel Aviv University
Location: 

University of British Columbia

Topic: 

The Elekes-Ronyai-Szabo theory and its applications

Description: 
Let F(x,y,z) be a real trivariate polynomial of constant degree, and let A,B,C be three sets of real numbers, each of size n.
 
How many roots can F have on A x B x C?
 
This setup arises in many interesting problems in combinatorial geometry, including distinct distances between points on curves, distinct distances from three points, collinear triples of points on curves (the `orchard problem'), unit-area triangles, triple intersection points of families of circles, and more.
 
This question has been studied by Elekes and R\'onyai and then by Elekes and Szab\'o about 15 years ago. One of their striking results is that, for the special case where F(x,y,z) = z-f(x,y), either F vanishes at  only a subquadratic number (o(n^2)) of points of A x B x C, or else f must have one of the special forms f(x,y) = h(p(x)+q(y)) or f(x,y) = h(p(x)q(y)), for univariate polynomials p, q, h.
 
In this talk I will survey recent progress on this problem, in which the analysis is greatly simplified, and the bounds become sharp: If F does not have  a special form, the number of roots is at most O(n^{11/6}). Moreover, the results also hold over the complex field. This yields significantly improved bounds for many geometric problems, as listed above.
 
The proofs use techniques from algebra and algebraic geometry, which are somewhat related to the recent growing body of work on algebraic techniques for incidences and distance problems, inspired by Guth and Katz's seminal papers.
 
Joint work with Orit Raz, Jozsef Solymosi, and Frank de Zeeuw (and others).
Other Information: 

Location: ESB 4127