# Christoph Spiegel

### Ph.D. Student at the Universitat

Politècnica de Catalunya

Omega Building • room 412 • 08034 Barcelona

**supervisors** Juanjo Rué and Oriol Serra

**research area** additive combinatorics

#### submitted

**11. Independent Chains in Acyclic Posets**

We consider the problem of determining the maximum order of an induced vertex-disjoint union of cliques in a graph. More specifically, given some family of graphs $\mathcal{G}$ of equal order, we are interested in the parameter $a(\mathcal{G}) = \min_{G \in \mathcal{G}} \max \{ |U| : U \subseteq V, G[U] \text{ is a vertex-disjoint union of cliques} \}$. We determine the value of this parameter precisely when $\mathcal{G}$ is the family of comparability graphs of $n$-element posets with acyclic cover graph. In particular, we show that $a(\mathcal{G}) = (n+o(n))/\log_2 (n)$ in this class.

**10. On strong infinite Sidon and \(B_h\) sets and random sets of integers**

A set of integers \(S \subset \mathbb{N}\) is an \(\alpha\)-strong Sidon} set if the pairwise sums of its elements are far apart by a certain measure depending on \(\alpha\), more specifically if \( \big| (x+w) - (y+z) \big| \geq \max \{ x^{\alpha},y^{\alpha},z^{\alpha},w^\alpha \} \) for every \(x,y,z,w \in S\) satisfying \( \{x,w\} \neq \{y,z\}\). We obtain a new lower bound for the growth of \( \alpha \)-strong infinite Sidon sets when \( 0 \leq \alpha < 1 \). We also further extend that notion in a natural way by obtaining the first non-trivial bound for \( \alpha \)-strong infinite \( B_h \) sets. In both cases, we study the implications of these bounds for the density of, respectively, the largest Sidon or \( B_h \) set contained in a random infinite subset of \( \mathbb{N} \). Our theorems improve on previous results by Kohayakawa, Lee, Moreira and Rödl.

**9. An Erdős-Fuchs Theorem for Ordered Representation Functions**

Let $k\geq 2$ be a positive integer. We study concentration results for the ordered representation functions $r^{\leq}_k(\mathcal{A},n) = \# \big\{ (a_1 \leq \dots \leq a_k) \in \mathcal{A}^k : a_1+\dots+a_k = n \big\}$ and $r^{<}_k(\mathcal{A},n) = \# \big\{ (a_1 < \dots < a_k) \in \mathcal{A}^k : a_1+\dots+a_k = n \big\}$ for any infinite set of non-negative integers $\mathcal{A}$. Our main theorem is an Erdős-Fuchs-type result for both functions: for any $c > 0$ and $\star \in \{\leq,<\}$ we show that $\sum_{j = 0}^{n} \Big( r^{\star}_k (\mathcal{A},j) - c \Big)= o\big(n^{1/4}\log^{-1/2}n\big)$ is not possible. We also show that the mean squared error $E^\star_{k,c}(\mathcal{A},n)=\frac{1}{n} \sum_{j = 0}^{n} \Big( r^{\star}_k(\mathcal{A},j) - c \Big)^2$ satisfies $\limsup_{n \to \infty} E^\star_{k,c}(\mathcal{A},n)>0$. These results extend two theorems for the non-ordered representation function proved by Erdős and Fuchs in the case of $k=2$.

**8. On the Odd Cycle Game and Connected Rules**

We study the positional game where two players, Maker and Breaker, alternately select respectively 1 and b previously unclaimed edges of \( K_n \). Maker wins if she succeeds in claiming all edges of some odd cycle in Kn and Breaker wins otherwise. Improving on a result of Bednarska and Pikhurko, we show that Maker wins the odd cycle game if \( b \leq (4 - \sqrt{6})/5 +o(1) n \). We furthermore introduce “connected rules” and study the odd cycle game under them, both in the Maker-Breaker as well as in the Client-Waiter variant.

**7. Another Note on Intervals in the Hales-Jewett Theorem**

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.

#### published

**6. Additive Volume of Sets Contained in Few Arithmetic Progressions**

A conjecture of Freĭman 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.

G.A. Freĭman, O. Serra and C. Spiegel. Integers 19:#A34, 2019.

**5. A step beyond Freĭman’s theorem for set addition modulo a prime**

Freĭman'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}\).

**4. On a problem of Sárkőzy and Sós for multivariate linear forms**

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.

**3. On the optimality of the uniform random strategy**

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.

**2. A Note on Sparse Supersaturation and Extremal Results for Linear Homogeneous Systems**

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.

**1. Threshold functions and Poisson convergence for systems of equations in random sets**

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.

#### conference talks

**June 2019**GAPCOMB Workshop, Campelles

**June 2019**Postgraduate Combinatorial Conference, Oxford PDF

**June 2018**Discrete Mathematics Days, Sevilla PDF

**May 2018**Combinatorial and Additive Number Theory Conference, New York PDF

**September 2017**The Music of Numbers, Madrid PDF

**June 2017**Interactions with Combinatorics, Birmingham PDF

**March 2017**FUB-TAU Joint Workshop, Tel Aviv

#### seminar talks

**November 2019**Research Seminar Combinatorics, Berlin

**November 2019**Seminarvortrag, Ilmenau

**May 2019**PhD Seminar on Combinatorics, Games and Optimisation, London

**May 2019**Combinatorial Theory Seminar, Oxford

**February 2019**Extremal Set Theory Seminar, Budapest

**December 2018**Research Seminar Combinatorics, Berlin

**March 2018**GRAPHS@IMPA, Rio de Janeiro

**December 2017**Research Seminar Combinatorics, Berlin

**October 2017**LIMDA Joint Seminar, Barcelona

**Mai 2017**LIMDA Joint Seminar, Barcelona

**March 2016** LIMDA Joint Seminar, Barcelona

**Threshold functions for systems of equations in random sets**

We present a unified framework to deal with threshold functions for the existence of solutions to systems of linear equations in random sets. This covers the study of several fundamental combinatorial families such as \(k\)-arithmetic progressions, \(k\)-sum-free sets, \(B_{h}[g]\) sequences and Hilbert cubes of dimension \(k\). We show that there exists a threshold function for the property "\(\mathcal{A}^m\) contains a non-trivial solution of \(M\cdot \textbf{x}=\textbf{0}\)” where \(\mathcal{A}\) is a random set. This threshold function depends on a parameter maximized over all subsystems, a notion previously introduced by Rödl and Ruciński. The talk will contain a formal definition of trivial solutions for any combinatorial structure, extending a previous definition by Ruzsa.

*Joint work with Juanjo Rué and Ana Zumalacárregui.*

**January 2016** Research Seminar Combinatorics, Berlin

**Van der Waerden Games**

József Beck defines the (weak) Van der Waerden game as follows: two players alternately pick previously unpicked integers of the interval \( \{1, 2,... , n\} \). The first player wins if he has selected all members of a \(k\)-term arithmetic progression. We present his 1981 result that \( 2^{k - 7 k^{7/8}} < W^{\star} (k) < k^{3} 2^{k-2} \) where \( W^{\star} (k) \) is the least integer \( n \) so that the first player has a winning strategy.

**December 2015** "What is...?" Seminar Series, Berlin

**What is ... Discrete Fourier Analysis?**

Discrete Fourier analysis can be a powerful tool when studying the additive structure of sets. Sets whose characteristic functions have very small Fourier coefficients act like pseudo-random sets. On the other hand well structured sets (such as arithmetic progressions) have characteristic functions with a large Fourier coefficient. This dichotomy plays an integral role in many proofs in additive combinatorics from Roth’s Theorem and Gower’s proof of Szemerédi’s Theorem up to the celebrated Green-Tao Theorem. We will introduce the discrete Fourier transform of (balanced) characteristic functions of sets as well some basic properties, inequalities and exercises.

*Introductory talk before Julia Wolf's lecture at the Sofia Kovalevskaya Colloquium.*

**October 2015** Research Seminar Combinatorics, Berlin

**Threshold functions for systems of equations in random sets**

We present a unified framework to deal with threshold functions for the existence of certain combinatorial structures in random sets. The structures will be given by certain linear systems of equations \(M\cdot \textbf{x} = 0\) and we will use the binomial random set model where each element is chosen independently with the same probability. This covers the study of several fundamental combinatorial families such as \(k\)-arithmetic progressions, \(k\)-sum-free sets, \(B_{h}[g]\) sequences and Hilbert cubes of dimension \(k\). Furthermore, our results extend previous ones about \(B_h[2]\) sequences by Godbole et al.

We show that there exists a threshold function for the property *"\(\mathcal{A}^m\) contains a non-trivial solution of \(M\cdot \textbf{x}=\textbf{0}\)"* where \(\mathcal{A}\) is a random set. This threshold function depends on a parameter maximized over all subsystems, a notion previously introduced by Rödl and Ruciński. The talk will contain a formal definition of trivial solutions for any combinatorial structure, extending a previous definition by Ruzsa. Furthermore, we will study the behavior of the distribution of the number of non-trivial solutions in 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.

*Joint work with Juanjo Rué and Ana Zumalacárregui.*

#### 2019

**October 2019** Growth in Finite and Infinite Groups, Oberwolfach

**September 2019** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelsmaue

**June 2019** GAPCOMB Workshop, Campelles

**June 2019** Postgraduate Combinatorial Conference, Oxford

**May 2019** One-Day Meeting in Combinatorics, Oxford

#### 2018

**September 2018** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelsmaue

**June 2018** Discrete Mathematics Days, Sevilla

**May 2018** Combinatorial and Additive Number Theory Conference, New York

**May 2018** Georgia Discrete Analysis Conference, Athens

**March 2018** Graphs and Randomness, Rio de Janeiro

#### 2017

**October 2017** BMS-BGSMath Junior Meeting, Barcelona

**September 2017** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelsmaue

**September 2017** The Music of Numbers, Madrid

**June 2017** Interactions with Combinatorics, Birmingham

**May – June 2017** Random Discrete Structures, Barcelona

**April – May 2017** Interactions of harmonic analysis, combinatorics and number theory, Barcelona

**March 2017** FUB-TAU Joint Workshop, Tel Aviv

**January 2017** SODA17, ANALCO17 and ALENEX17, Barcelona

#### 2016

**September 2016** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelsmaue

**July 2016** Symposium Diskrete Mathematik, Berlin

**July 2016** Discrete Mathematics Days Barcelona, Barcelona

**February 2016** PosGames2016, Berlin

**January 2016** Combinatorial and Additive Number Theory, Graz

#### 2014 – 2015

**September 2015** Cargèse Fall School on Random Graphs

**September 2015** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Vysoká Lípa

**May 2015** Berlin-Poznan-Hamburg Seminar: 20th Anniversary, Berlin

**October 2014** Methods in Discrete Structures Block Course: Towards the Polynomial Freĭman-Ruzsa Conjecture, Berlin

#### at Universitat Politècnica de Catalunya

**Autumn 2018** Tutor for Discrete Mathematics and Optimization

**Autumn 2017** Tutor for Discrete Mathematics and Optimization

#### at Freie Universität Berlin

**Winter 2013/14** Tutor for Analysis I

**Summer 2012** Tutor for Analysis II

**Summer 2011** Tutor for Analysis I

**March 2015** Master of Science at Freie Universität Berlin

*Approximating Primitive Integrals and Aircraft Performance*(09/2014 - 03/2015) in the area of Graph Theory and Optimization under the supervision of Prof. Dr. Ralf Borndörfer. The research was part of the Flight Trajectory Optimization on Airway Networks project at the Zuse-Institute Berlin (ZIB). The main industry partner of this project is Lufthansa Systems Frankfurt. Furthermore it is part of the joint project

*E-Motion - Energieeffiziente Mobilität*which is funded by the German Ministry of Education and Research (BMBF).During the course of my research I was employed as a student research assistant at the ZIB (05/2014 - 03/2015).

**September 2012** Bachelor of Science at Freie Universität Berlin

*Numerical Pricing of Financial Derivatives*(06/2012 - 09/2012) under the supervision of Prof. Dr. Carsten Hartmann.

**Juni 2009** Abitur at Canisius-Kolleg Berlin