Maximilian Wötzel defended his PhD thesis Probabilistic and extremal studies in additive combinatorics, supervised jointly by Juanjo Rué and Oriol Serra, on 26 January 2022 within the UPC doctoral program in Applied Mathematics. Currently he is in the group of Ross Kang at the Radboud University in Nijmegen, Netherlands.
Thesis summary
The general goal in additive combinatorics —historically also called combinatorial or additive number theory— is to study the additive structure of sets in certain ambient groups. Extremal combinatorics studies how large a collection of finite objects can be before exhibiting certain structural requirements. Probabilistic combinatorics analyzes random combinatorial structures, identifying in particular the structure of typical combinatorial objects. Among the most celebrated outputs is the study of random graphs initiated by Erdős and Rényi. A particularly striking example of how these three areas interweave is the development by Erdős of the probabilistic method in number theory and in combinatorics, which exhibits the existence of many extremal structures in additive settings using probabilistic means. The topics in this thesis all lie in the intersection of these three areas, and concern the following problems.
Integer solutions to systems of linear equations. The study of how large a subset of the integers can be before containing solutions to a given system of linear equations is a classical topic in additive number theory. Recent years have seen a lot of developments regarding threshold results for certain integer solutions to an arbitrary given system of linear equations, answering the question when one expects the binomial random subset of an initial segment of integers to contain solutions almost surely. The next logical question is the following. Suppose we are in the range that there will exist integer solutions in the binomial random set, how are these solutions distributed? The first chapter of the thesis takes steps towards answering this question by providing sufficient conditions for when a wide variety of solutions follow a normal distribution. Furthermore, it is discussed how, in certain cases, these sufficient conditions are also necessary.
Independent sets in hypergraphs. The method of hypergraph containers is a very general tool introduced independently by Balogh, Morris and Samotij and Saxton and Thomason that can be used to obtain results on the number and structure of independent sets in hypergraphs. The connection with additive combinatorics appears because many additive problems can be encoded as study ing independent sets in hypergraphs. For instance, by defining the vertices of the hypergraphs to be the elements of an initial segment of the positive integers and the hyperedges as those elements that form solutions to a given system of linear equations, we have placed the problem studied in the first chapter into the setting of independent sets in hypergraphs. The second chapter of the thesis establishes an extension of a recent asymmetric version of the container method due to Morris, Samotij and Saxton to multipartite hypergraphs.
Sets with bounded sumset. What can be said about the structure of two finite sets in an abelian group if their Minkowski sum is not much larger than the sets themselves? A classical result by Kneser says that this can happen if and only if the Minkowski sum is periodic with respect to a proper subgroup. The third chapter of the thesis establishes two types of results. The first is so-called robust versions of classical theorems of Kneser and Freiman. Robust here refers to the fact that instead of asking for structural information on the constituent sets with the knowledge that their sumset is small, we only require that this holds for a large subset. The second part of the chapter concerns the typical structure of pairs of sets with small Minkowski sum, that is, what if we only want to give a structural statement for almost all pairs of sets with a sumset of a given size? We give an approximate structure theorem that holds for almost the complete range of possible sumset sizes that uses the hypergraph container framework introduced in the preceding chapter.
Sidon set systems. Sidon sets are subsets of abelian groups such that all pairwise sums of their elements are distinct and they are well-studied objects in additive number theory. Classical questions regarding Sidon sets are to determine their maximum size or to know when a random set is a Sidon set. In the final chapter of the thesis we generalize the notion of Sidon sets to set systems and establish the corresponding bounds for these two questions. We also prove a so-called relative density result conditional on a conjecture on the specific structure of maximal Sidon systems.
Highlighted publication. J. Rué, M. Wötzel : Normal limiting distributions for systems of linear equations in random sets. Linear Algebra and its Applications 649 (2022). Article.