Citation
Pohoata, Andrei Cosmin (2020) Extremal Results in and out of Additive Combinatorics. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/mb11pg80. https://resolver.caltech.edu/CaltechTHESIS:05232020121812350
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 twovariate 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 sumproduct 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 progressionfree 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 ℤ_{4}^{n} and in higher order 2abelian groups. Their new polynomial method was quickly adapted by Ellenberg and Gijswijt to show a similar strong result for the size of the largest threeterm progression free subset of 𝔽_{q}^{n} where q is an odd prime power, the socalled 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 multilayered polynomial method approach to derive improved bounds for the largest threeterm progression free set in ℤ_{8}^{n} (which also improve on the CrootLevPach bounds for a large family of higher order 2abelian groups). In Chapter 5, we generalize the EllenbergGijswijt bound for the cap set problem to random progressionfree subsets of 𝔽_{q}^{n}, improving on a theorem of Tao and Vu. A result of this type enables one to find four term progressionsfree sets which contain threeterm progressions in all of their large subsets (with good quantitative bounds), but which do not contain too many threeterm 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 4APfree set. We show in general, for all fixed integers k > s ≥ 3, that if f_{s,k}(n) denotes the maximum possible number of sterm arithmetic progressions in a set of n integers which contains no kterm arithmetic progression, then f_{s,k}(n) = n^{2o(1)}. This answers an old question of Erdős. In Chapter 7, we study some limitations of the CrootLevPach 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 CrootLevPach method.
Item Type:  Thesis (Dissertation (Ph.D.))  

Subject Keywords:  Local properties, ErdosGyarfas, expanding polynomials, progressionfree sets, polynomial method, CrootLevPach, Erdos  
Degree Grantor:  California Institute of Technology  
Division:  Physics, Mathematics and Astronomy  
Major Option:  Mathematics  
Awards:  Scott Russell Johnson Graduate Dissertation Prize in Mathematics, 2020. Apostol Award for Excellence in Teaching in Mathematics, 2016, 2019.  
Thesis Availability:  Public (worldwide access)  
Research Advisor(s): 
 
Thesis Committee: 
 
Defense Date:  21 May 2020  
Record Number:  CaltechTHESIS:05232020121812350  
Persistent URL:  https://resolver.caltech.edu/CaltechTHESIS:05232020121812350  
DOI:  10.7907/mb11pg80  
Related URLs: 
 
ORCID: 
 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  13719  
Collection:  CaltechTHESIS  
Deposited By:  Andrei Pohoata  
Deposited On:  01 Jun 2020 22:12  
Last Modified:  12 Jun 2020 19:03 
Thesis Files

PDF
 Final Version
See Usage Policy. 672kB 
Repository Staff Only: item control page