Christoph Spiegel

Ph.D. Student at the Universitat
Politècnica de Catalunya

Universitat Politècnica de Catalunya
Omega Building • room 412 • 08034 Barcelona
christoph.spiegel@upc.edu

supervisorsJuanjo Rué Perna and Oriol Serra
research area   additive combinatorics

Publications

P. Candela, O. Serra and C. Spiegel

A step beyond Freiman’s theorem for set addition modulo a prime

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}\).

arXiv:1805.12374

J. Rué Perna and C. Spiegel

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.

arXiv:1802.07597

C. Kusch, J. Rué Perna, C. Spiegel and T. Szabó

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.

accepted by Random Structures and Algorithms and available on arXiv:1711.07251

C. Spiegel

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.

The Electronic Journal of Combinatorics 24(3):#P3.38, 2017

J. Rué Perna, C. Spiegel and A. Zumalacárregui

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.

Mathematische Zeitschrift 288 (1-2):333-360, February 2018
Talks

conference talks

June 2018Discrete Mathematics Days, Sevilla   PDF

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

September 2017The Music of Numbers, Madrid   PDF

June 2017Interactions with Combinatorics, Birmingham   PDF

March 2017FUB-TAU Joint Workshop, Tel Aviv


seminar talks

March 2018GRAPHS@IMPA, Rio de Janeiro

December 2017Research Seminar Combinatorics, Berlin

October 2017LIMDA Joint Seminar, Barcelona

Mai 2017LIMDA Joint Seminar, Barcelona

March 2016LIMDA 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 2016Research 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 2015Research 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.

Conferences and Workshops

2018

June 2018Discrete Mathematics Days, Sevilla

May 2018Combinatorial and Additive Number Theory Conference, New York

May 2018Georgia Discrete Analysis Conference, Athens

March 2018Graphs and Randomness, Rio de Janeiro


2017

October 2017BMS-BGSMath Junior Meeting, Barcelona

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

September 2017The Music of Numbers, Madrid

June 2017Interactions with Combinatorics, Birmingham

May – June 2017Random Discrete Structures, Barcelona

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

March 2017FUB-TAU Joint Workshop, Tel Aviv

January 2017SODA17, ANALCO17 and ALENEX17, Barcelona


2016

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

July 2016Symposium Diskrete Mathematik, Berlin

July 2016Discrete Mathematics Days Barcelona, Barcelona

February 2016PosGames2016, Berlin

January 2016Combinatorial and Additive Number Theory, Graz


2014 – 2015

September 2015Cargèse Fall School on Random Graphs

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

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

October 2014Methods in Discrete Structures Block Course: Towards the Polynomial Freiman-Ruzsa Conjecture, Berlin

Teaching

at Universitat Politècnica de Catalunya

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

Education

March 2015  Master of Science at Freie Universität Berlin

I wrote my master thesis on 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

I wrote my bachelor thesis on Numerical Pricing of Financial Derivatives (06/2012 - 09/2012) under the supervision of Prof. Dr. Carsten Hartmann.

Juni 2009  Abitur at Canisius-Kolleg Berlin

Fun Stuff

Some conference posters I have designed: