Algebraic and Analytic Methods in Combinatorics: Expanding polynomials and the Elekes-Szabó problem using proximity
Presenter
March 17, 2025
Keywords:
- extremal combinatorics
- extremal graph theory
- probabilistic combinatorics
- discrete geometry
- additive combinatorics
- combinatorial geometry
- incidence geometry
- arithmetic progressions
- Discrete analysis
MSC:
- 05C25 - Graphs and abstract algebra (groups rings fields
- etc.) [See also 20F65]
- 05C35 - Extremal problems in graph theory [See also 90C35]
- 05C50 - Graphs and linear algebra (matrices eigenvalues etc.)
- 05D40 - Probabilistic methods in extremal combinatorics including polynomial methods (combinatorial Nullstellensatz etc.)
- 52C35 - Arrangements of points flats hyperplanes (aspects of discrete geometry) [See also 14N20 32S22]
Abstract
Elekes and Rónyai proved that if P(x,y) is a polynomial, then either P has a very special structure (for example P(x,y) = x+y or P(x,y) = xy), or else for every pair of sets A, B \subset R of size n, P(A x B) has cardinality substantially larger than n. This result was generalized by Elekes and Szabó, who proved that if Z \subset R^3 is an algebraic variety, then either Z has a very special structure (for example Z is a plane), or else for every triples of sets A, B, C \subset R of size n, Z \cap (A x B x C) has cardinality substantially smaller than n^2.
The Elekes-Rónyai and Elekes-Szabó theorems have applications to extremal questions in incidence geometry. There have been several generalizations of the above results, and several quantitative improvements that have strengthened the exponent in the Elekes-Szabó theorem from n^2 to n^{2-c} for various explicit values of c > 0 (and similarly for the Elekes-Rónyai theorem). I will discuss some ideas that give further quantitative improvements for this problem, leading to the exponent c = 2/7. This is joint work with Jozsef Solymosi.