Christoph Spiegel

The Hales-Jewett Theorem states that any \(r\)-colouring of \([m]^n\) contains a monochromatic combinatorial line if \(n\) is large enough. Shelah's proof of the theorem implies that for \(m = 3\) there always exists a monochromatic combinatorial lines whose set of active coordinates is the union of at most \(r\) intervals. Conlon and Kamčev proved the existence of colourings for which it cannot be fewer than \(r\) intervals if \(r\) is odd. For \(r = 2\) however, Leader and Räty showed that one can always find a monochromatic combinatorial line whose active coordinate set is a single interval. In this paper, we extend the result of Leader and Räty to the case of all even \(r\)=, showing that one can always find a monochromatic combinatorial line in \([3]^n\) whose set of active coordinate is the union of at most \(r-1\) intervals.

A conjecture of Freiman gives an exact formula for the largest volume of a finite set \(A\) of integers with given cardinality \(k = |A|\) and doubling \(T = |2A|\). The formula is known to hold when \(T \le 3k-4\), for some small range over \(3k-4\) and for families of structured sets called chains. In this paper we extend the formula to sets of every dimension and prove it for sets composed of three segments, giving structural results for the extremal case. A weaker extension to sets composed of a bounded number of segments is also discussed.

Freiman's 2.4-Theorem states that any set \(A \subset \mathbb{Z}_p\) satisfying \(|2A| \leq 2.4|A| - 3 \) and \(|A| < p/35\) can be covered by an arithmetic progression of length at most \(|2A| - |A| + 1\). A more general result of Green and Ruzsa implies that this covering property holds for any set satisfying \(|2A| \leq 3|A| - 4\) as long as the rather strong density requirement \(|A| < p/10^{215}\) is satisfied. We present a version of this statement that allows for sets satisfying \(|2A| \leq 2.48|A| - 7\) with the more modest density requirement of \(|A| < p/10^{10}\).

We prove that for pairwise co-prime numbers \(k_1,\dots,k_d \geq 2\) there does not exist any infinite set of positive integers \(A\) such that the representation function \(r_A (n) = \{ (a_1, \dots, a_d) \in A^d : k_1 a_1 + \dots + k_d a_d = n \}\) becomes constant for \(n\) large enough. This result is a particular case of our main theorem, which poses a further step towards answering a question of Sárkőzy and Sós and widely extends a previous result of Cilleruelo and Rué for bivariate linear forms.

The concept of biased Maker-Breaker games, introduced by Chvátal and Erdős, is a central topic in the field of positional games, with deep connections to the theory of random structures. For any given hypergraph \(\cal H\) the main questions is to determine the smallest bias \(q({\cal H})\) that allows Breaker to force that Maker ends up with an independent set of \(\cal H\). Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies a couple of natural `container-type' regularity conditions about the degree of subsets of its vertices. This will enable us to derive a hypergraph generalization of the \(H\)-building games, studied for graphs by Bednarska and Łuczak. Furthermore, we investigate the biased version of generalizations of the van der Waerden games introduced by Beck. We refer to these generalizations as Rado games and determine their threshold bias up to constant factors by applying our general criteria. We find it quite remarkable that a purely game theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, when the generalizations to hypergraphs in the analogous setup of sparse random discrete structures are usually quite challenging.

We study the thresholds for the property of containing a solution to a linear homogeneous system in random sets. We expand a previous sparse Szémeredi-type result of Schacht to the broadest class of matrices possible. We also provide a shorter proof of a sparse Rado result of Friedgut, Rödl, Ruciński and Schacht based on a hypergraph container approach due to Nenadov and Steger. Lastly we further extend these results to include some solutions with repeated entries using a notion of non-trivial solutions due to Ruzsa as well as Rué et al.

We present a unified framework to study threshold functions for the existence of solutions to linear systems of equations in random sets which includes arithmetic progressions, sum-free sets, \(B_{h}[g]\)-sets and Hilbert cubes. In particular, we show that there exists a threshold function for the property "\(\mathcal{A}\) contains a non-trivial solution of \(M\cdot\textbf{x}=\textbf{0}\)", where \(\mathcal{A}\) is a random set and each of its elements is chosen independently with the same probability from the interval of integers \(\{1,\dots,n\}\). Our study contains a formal definition of trivial solutions for any combinatorial structure, extending a previous definition by Ruzsa when dealing with a single equation. Furthermore, we study the behaviour of the distribution of the number of non-trivial solutions at the threshold scale. We show that it converges to a Poisson distribution whose parameter depends on the volumes of certain convex polytopes arising from the linear system under study as well as the symmetry inherent in the structures, which we formally define and characterize.