Combinatorics Semnar

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(n^2) 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(n^11/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. If time allows, I will discuss an application of this kind to the following problem: Given n points lying on a d-dimensional algebraic variety in R^D, 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 Erdos from 1957, studied recently by Conlon et al. 

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