# Christoph Spiegel

### Ph.D. Student at the Universitat

Politècnica de Catalunya

Omega Building • room 412 • 08034 Barcelona

**supervisor** Juanjo Rué Perna

**research interests** combinatorial number theory

**to be submitted** Random Strategies are Nearly Optimal for Generalized

van der Waerden Games – with C. Kusch, J. Rué Perna and T. Szabó

We study the biased version of a strong generalization of the van der Waerden games introduced by Beck as well as the hypergraph generalization of the biased \(H\)-games previously studied by Bednarska and Łuczak. In particular, we determine the threshold biases of these games up to constant factors by proving general winning criteria for Maker and Breaker based on the ideas of Bednarska and Łuczak. We show that a random strategy for Maker is the best known strategy.

**submitted** 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 Rúzsa as well as Rué et al.

*Note that simultaneous and independent work of Hancock, Staden and Treglown covers some of the same results.*

**to be submitted** On the asymptotic proportion

of monochromatic combinatorial lines – with L. Vena

**to appear** Threshold functions and Poisson convergence for systems

of equations in random sets – with J. Rué Perna and A. Zumalacárregui

**Accepted by Mathematisch Zeitschrift – Feburary 2017**

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.

**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é Perna 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é Perna and Ana Zumalacárregui.*

#### future

**August 2017** Eurocomb 2017, Vienna

**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

#### past

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

**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

**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 Freiman-Ruzsa Conjecture, Berlin

**Winter 2013/14** Analysis I (Tutor) at Freie Universität Berlin

**Summer 2012** Analysis II (Tutor) at Freie Universität Berlin

**Summer 2011** Analysis I (Tutor) at Freie Universität Berlin

**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

You should check out FURIOS where I have worked on all sorts of things.

You can also find some of my photography on facebook and flickr.

Also check out Shagnik Das and Clément Requilé

Some conference posters I have designed: