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
Orit Raz
Tel Aviv University
Title: Polynomials vanishing on Cartesian products

Abstract: 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 question has been studied by Elekes and Rónyai and then by Elekes and Szabó 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 o(n2) number 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 the talk I will discuss several recent results, 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(n11/6). The results also hold over the complex field.

This setup arises in various Erd?s-type problems in combinatorial geometry, and the result provides a unified tool for their analysis. I will discuss an application of this kind to the following problem: Given n points lying on a d-dimensional algebraic variety in RD, show that there always exists a large subset S, such that all the distances spanned by pairs of points of S are distinct. This is a variant of a question of Erd?s from 1957, studied recently by Conlon et al.

Based on joint works with Micha Sharir, Jozsef Solymosi, and Frank de Zeeuw.

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