Additive structures and randomness in combinatorics

• Autores: Christoph Stefan Spiegel
• Directores de la Tesis: Juanjo Rué Perna (dir. tes.) , Oriol Serra Albó (codir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2020
• Idioma: español
• Texto completo no disponible (Saber más ...)
• Resumen

  • Arithmetic Combinatorics, Combinatorial Number Theory, Structural Additive Theory and Additive Number Theory are just some of the terms used to describe the vast field that sits at the intersection of Number Theory and Combinatorics and which will be the focus of this thesis. Its contents are divided into two main parts, each containing several thematically related results.

    The first part deals with the question under what circumstances solutions to arbitrary linear systems of equations usually occur in combinatorial structures..The properties we will be interested in studying in this part relate to the solutions to linear systems of equations.

    A first question one might ask concerns the point at which sets of a given size will typically contain a solution. We will establish a threshold and also study the distribution of the number of solutions at that threshold, showing that it converges to a Poisson distribution in certain cases.

    Next, Van der Waerden’s Theorem, stating that every finite coloring of the integers contains monochromatic arithmetic progression of arbitrary length, is by some considered to be the first result in Ramsey Theory. Rado generalized van der Waerden’s result by characterizing those linear systems whose solutions satisfy a similar property and Szemerédi strengthened it to a statement concerning density rather than colorings. We will turn our attention towards versions of Rado’s and Szemerédi’s Theorem in random sets, extending previous work of Friedgut, Rödl, Rucin´ski and Schacht in the case of the former and of Conlon, Gowers and Schacht for the latter to include a larger variety of systems and solutions.

    Lastly, Chvátal and Erdo¿s suggested studying Maker-Breaker games. These games have deep connections to the theory of random structures and we will build on work of Bednarska and Luczak to establish the threshold for how much a large variety of games need to be biased in favor of the second player. These include games in which the first player wants to occupy a solution to some given linear system, generalizing the van der Waerden games introduced by Beck.

    The second part deals with the extremal behavior of sets with interesting additive properties. In particular, we will be interested in bounds or structural descriptions for sets exhibiting some restrictions with regards to either their representation function or their sumset.

    First, we will consider Sidon sets, that is sets of integers with pairwise unique differences. We will study a generalization of Sidon sets proposed very recently by Kohayakawa, Lee, Moreira and Rödl, where the pairwise differences are not just distinct, but in fact far apart by a certain measure. We will obtain strong lower bounds for such infinite sets using an approach of Cilleruelo. As a consequence of these bounds, we will also obtain the best current lower bound for Sidon sets in randomly generated infinite sets of integers of high density.

    Next, one of the central results at the intersection of Combinatorics and Number Theory is the Freiman–Ruzsa Theorem stating that any finite set of integers of given doubling can be efficiently covered by a generalized arithmetic progression. In the case of particularly small doubling, more precise structural descriptions exist. We will first study results going beyond Freiman’s well-known 3k–4 Theorem in the integers. We will then see an application of these results to sets of small doubling in finite cyclic groups.

    Lastly, we will turn our attention towards sets with near-constant representation functions. Erdo¿s and Fuchs established that representation functions of arbitrary sets of integers cannot be too close to being constant. We will first extend the result of Erdo¿s and Fuchs to ordered representation functions. We will then address a related question of Sárközy and Sós regarding weighted representation function.