Extremal Results in and out of Additive Combinatorics

Citation

Pohoata, Andrei Cosmin (2020) Extremal Results in and out of Additive Combinatorics. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/mb11-pg80. https://resolver.caltech.edu/CaltechTHESIS:05232020-121812350

Abstract

In this thesis, we study several related topics in extremal combinatorics, all tied together by various themes from additive combinatorics and combinatorial geometry.

First, we discuss some extremal problems where local properties are used to derive global properties. That is, we consider a given configuration where every small piece of the configuration satisfies some restriction, and use this local property to derive global properties of the entire configuration. We study one such Ramsey problem of Erdős and Shelah, where the configurations are complete graphs with colored edges and every small induced subgraph contains many distinct colors. Our bounds for this Ramsey problem show that the known probabilistic construction is tight in various cases. We study one discrete geometry variant, also by Erdős, where we have a set of points in the plane such that every small subset spans many distinct distances. Finally, we consider an arithmetic variant, suggested by Dvir, where we are given sets of real numbers such that every small subset has a large difference set. In Chapter 2, we derive new bounds for all of the above problems. Along the way, we also essentially answer a question of Erdős and Gyárfás.

Second, we study the behavior of expanding polynomials on sets with additive or multiplicative structure. Given an arbitrary set of real numbers A and a two-variate polynomial f with real coefficients, a remarkable theorem of Elekes and Rónyai from 2000 states that the size |f(A,A)| of the image of f on the cartesian product A × A grows asymptotically faster than |A|, unless f exhibits additive or multiplicative structure. Finding the best quantitative bounds for this intriguing phenomenon (and for variants of it) has generated a lot of interest over the years due to its intimate connection with the sum-product problem in additive combinatorics. In Chapter 3, we discuss new bounds for |f(A,A)| when the set A has few sums or few products.

Another central problem in additive combinatorics is the problem of finding good quantitative bounds for maximal progression-free sets in the integers (or various other groups). In 2017, a major breakthrough of Croot, Lev and Pach took the community by surprise with impressive new bounds for the problem in ℤ₄ⁿ and in higher order 2-abelian groups. Their new polynomial method was quickly adapted by Ellenberg and Gijswijt to show a similar strong result for the size of the largest three-term progression free subset of 𝔽_qⁿ where q is an odd prime power, the so-called cap set problem. This new set of ideas has subsequently led to very exciting developments in a vast range of topics. The rest of the thesis will be dedicated to discussing my joint results around these new developents. In Chapter 4, we develop a new multi-layered polynomial method approach to derive improved bounds for the largest three-term progression free set in ℤ₈ⁿ (which also improve on the Croot-Lev-Pach bounds for a large family of higher order 2-abelian groups). In Chapter 5, we generalize the Ellenberg-Gijswijt bound for the cap set problem to random progression-free subsets of 𝔽_qⁿ, improving on a theorem of Tao and Vu. A result of this type enables one to find four term progressions-free sets which contain three-term progressions in all of their large subsets (with good quantitative bounds), but which do not contain too many three-term progressions overall. Motivated by this application, in Chapter 6 we continue this investigation and study further the question of determining the maximum total number of 3APs in a given 4AP-free set. We show in general, for all fixed integers k > s ≥ 3, that if f_s,k(n) denotes the maximum possible number of s-term arithmetic progressions in a set of n integers which contains no k-term arithmetic progression, then f_s,k(n) = n^2-o(1). This answers an old question of Erdős. In Chapter 7, we study some limitations of the Croot-Lev-Pach approach and discuss some problems at the intersection of extremal set theory and combinatorial geometry where one can use additional linear algebraic ideas to go slightly beyond the Croot-Lev-Pach method.

Thesis Files