Additive structures and randomness in combinatorics

Abstract

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.

La combinatòria aritmètica, la teoria combinatòria dels nombres, la teoria additiva estructural i la teoria additiva de nombres són alguns dels termes que es fan servir per descriure una branca extensa i activa que es troba en la intersecció de la teoria de nombres i de la combinatòria, i que serà el motiu d'aquesta tesi doctoral. La primera part tracta la qüestió de sota quines circumstàncies es solen produir solucions a sistemes lineals d’equacions arbitràries en estructures additives. Una primera pregunta que s'estudia es refereix al punt en que conjunts d’una mida determinada contindran normalment una solució. Establirem un llindar i estudiarem també la distribució del nombre de solucions en aquest llindar, tot demostrant que en certs casos aquesta distribució convergeix a una distribució de Poisson. El següent tema de la tesis es relaciona amb el teorema de Van der Waerden, que afirma que cada coloració finita dels nombres enters conté una progressió aritmètica monocromàtica de longitud arbitrària. Aquest es considera el primer resultat en la teoria de Ramsey. Rado va generalitzar el resultat de van der Waerden tot caracteritzant en aquells sistemes lineals les solucions de les quals satisfan una propietat similar i Szemerédi la va reforçar amb una versió de densitat del resultat. Centrarem la nostra atenció cap a versions del teorema de Rado i Szemerédi en conjunts aleatoris, ampliant els treballs anteriors de Friedgut, Rödl, Rucinski i Schacht i de Conlon, Gowers i Schacht. Per últim, Chvátal i Erdos van suggerir estudiar estudiar jocs posicionals del tipus Maker-Breaker. Aquests jocs tenen una connexió profunda amb la teoria de les estructures aleatòries i ens basarem en el treball de Bednarska i Luczak per establir el llindar de la quantitat que necessitem per analitzar una gran varietat de jocs en favor del segon jugador. S'inclouen jocs en què el primer jugador vol ocupar una solució d'un sistema lineal d'equacions donat, generalitzant els jocs de van der Waerden introduïts per Beck. La segona part de la tesis tracta sobre el comportament extrem dels conjunts amb propietats additives interessants. Primer, considerarem els conjunts de Sidon, és a dir, conjunts d’enters amb diferències úniques quan es consideren parelles d'elements. Estudiarem una generalització dels conjunts de Sidons proposats recentment per Kohayakawa, Lee, Moreira i Rödl, en que les diferències entre parelles no són només diferents, sinó que, en realitat, estan allunyades una certa proporció en relació a l'element més gran. Obtindrem límits més baixos per a conjunts infinits que els obtinguts pels anteriors autors tot usant una construcció de conjunts de Sidon infinits deguda a Cilleruelo. Com a conseqüència d'aquests límits, obtindrem també el millor límit inferior actual per als conjunts de Sidon en conjunts infinits generats aleatòriament de nombres enters d'alta densitat. A continuació, un dels resultats centrals a la intersecció de la combinatòria i la teoria dels nombres és el teorema de Freiman-Ruzsa, que afirma que el conjunt suma d'un conjunt finit d’enters donats pot ser cobert de manera eficient per una progressió aritmètica generalitzada. En el cas de que el conjunt suma sigui de mida petita, existeixen descripcions estructurals més precises. Primer estudiarem els resultats que van més enllà del conegut teorema de Freiman 3k-4 en els enters. Llavors veurem una aplicació d’aquests resultats a conjunts de dobles petits en grups cíclics finits. Finalment, dirigirem l’atenció cap a conjunts amb funcions de representació gairebé constants. Erdos i Fuchs van establir que les funcions de representació de conjunts arbitraris d’enters no poden estar massa a prop de ser constants. Primer estendrem el resultat d’Erdos i Fuchs a funcions de representació ordenades. A continuació, abordarem una pregunta relacionada de Sárközy i Sós sobre funció de representació ponderada.