IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

10 Distinguished Lectures

NSF-CBMS Conference on Additive Combinatorics from a Geometric Viewpoint

May 21-25, 2018

University of South Carolina
Columbia, SC 29208

Application Deadline: January 31, 2018


During the week-long conference, the Distinguished Lecturer, Dr. Jozsef Solymosi (University of British Columbia), will present 10 lectures on additive combinatorics from a geometric viewpoint. Following is an out line of each planned lecture:

(1) Additive structures in subsets of integers. Hilbert cubes, Schur's theorem and other coloring questions. When can we expect density version of a coloring problem? Density of integer sequences. In additive combinatorics one of the basic questions what can we say about the structure of sets with small sumsets. A special case is when we are considering a partitioning of the first n integers into a few partition classes. (Or, colouring the integers, which is an equivalent formulation of the problem.) The oldest result is due to Hilbert, who proved that any coloring of the integers contains a "Hilbert-cube". Schur's theorem points to stronger statements, however there the statements only hold for the coloring (partitioning) problems, no density variants hold.

(2) The geometry of Cartesian products. Szemeredi-Trotter type incidence bounds for Cartesian products. Complex lines. Grid-like Cartesian products are easier to work with than with general pointsets. They offer to state and prove toy versions of harder to prove general theorems. Still, in several applications the Cartesian product structure appears naturally, so the results can be used in additive combinatorics directly.

(3) Sets with small doubling numbers. Sum of convex sets. Distinct consecutive differences imply large sumset. The sum-product problem. Continuation of the previous lecture for a better understanding of the additive structure of sets with small sumsets. We say a few words about the incompatibility of additive and multiplicative structures.

(4) Introduction to Freiman's theorem. Freiman's dimension lemma and its consequences. A tool: Schmidt's Subspace Theorem. When a set has very small doubling then it has a structure similar to a (generalized) arithmetic progression. We are going to use some heavy tools from algebraic geometry to prove some interesting results.

(5) Quasirandomness. Spectral methods in graphs. When can we use the spectra? Large sets in finite fields. Quasirandomness is an important tool in additive combinatorics. We introduce the notation of quasirandomness to Cayley graphs. Then we use some basic Cheeger-type inequalities to prove results on large subsets of finite fields.

(6) Dense graphs. Regularity and regularity lemmas for graphs and hypergraphs. When one uses dense graphs for modelling problems in additive combinatorics, then one of the most powerful tools is Szemeredi's Regularity Lemma. An even more powerful recent result is the Removal Lemma for hypergraphs. In this lecture we introduce the basic definitions and state various forms of the theorems.

(7) Applications of regularity. The corner theorem in integer grids. The earliest application of concept of regularity appeared in Szemeredi's proof on arithmetic progressions in dense subsets of integers. Then it became a frequently used technique in graph theory and theoretical computer science. We give a simple proof based on a variant of the hypergraph removal lemma. We will also talk about the Density Hales-Jewett theorem.

(8) Lines in space. A problem of Bourgain: bounds on joints. The polynomial method. Szekely's method on hard Erdos type problems. We are giving incidence bounds between points and lines in the plane and in space. We show some classical applications of the incidence bounds.

(9) The sum-product problem over fields of characteristic zero. An old conjecture of Erdos and Szemeredi states that for any finite set of integers has large sumset or large product set (almost quadratic in the size of the set). We are going to prove lower bounds on the sum of the cardinalities of the sumset and the product set showing that additive and multiplicative structures are very incompatible.

(10) The polynomial method over finite fields. The sum-product problem over finite fields. The Guth-Katz polynomial method is robust enough to extend it over finite fields. Then one can use it to derive incidence bounds there, which provide bounds on the sum-product problem over finite fields. There are important applications of the sumproduct phenomena in computer science.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC