Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
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 |