Talks take place at
Arnimallee 3, 14195 Berlin, room SR 210/A3, on Wednesdays, and
Arnimallee 3, 14195 Berlin, room SR 210/A3, on Thursdays.

Date	Speaker	Title
13.07.2016 16:15	Boris Bukh Carnegie Mellon University	One-sided epsilon-approximants.
07.07.2016 10:15	Anita Liebenau Monash University	Ramsey equivalence of $K_n$ and $K_n + K_{n−1}$.
29.06.2016 16:15	Benny Sudakov ETH Zürich	Equiangular lines and spherical codes in Euclidean spaces.
23.06.2016 10:15	Dániel Korándi ETH Zürich	Saturation in random graphs.
02.06.2016 10:15	Christian Reiher University of Hamburg	A Ramsey Class for Steiner Systems.
19.05.2016 10:15	Tuan Tran Czech Academy of Sciences	Structure and supersturation for intersecting families.
12.05.2016 10:15	Tibor Szabó FU Berlin	On the complexity of Ryser's Conjecture.
04.05.2016 16:15	Katherine Staden University of Warwick	The Erdős-Rothschild problem on edge-colourings.
27.04.2016 16:15	Dhruv Mubayi UI Chicago	Recent advances using the stepping up technique.
18.02.2016 10:15	Codruţ Grosu FU Berlin	A lower bound for the Towers of Hanoi game with more pegs.
11.02.2016 10:30	Mészáros Tamás FU Berlin	A conjecture on shattering-extremal set systems
04.02.2016 10:15	Christoph Spiegel FU Berlin	Van der Waerden Games - Part II
28.01.2016 10:15	Christoph Spiegel FU Berlin	Van der Waerden Games
21.01.2016 10:15	Giulia Codenotti FU Berlin	Kruskal-Katona and Macauley theorems in a relative setting
14.01.2016 10:15	Torsten Mütze TU Berlin	Bipartite Kneser graphs are Hamiltonian
10.12.2015 10:15	Julia Wolf University of Bristol	Counting monochromatic structures in finite abelian groups
03.12.2015 10:15	Shagnik Das FU Berlin	The Erdős-Rothschild problem for intersecting families
26.11.2015 10:15	József Balogh University of Illinois	On Some Recent Applications of the Container Method
19.11.2015 10:15	Olaf Parczyk Goethe Universität Frankfurt	Universality in random and sparse hypergraphs
10.11.2015 10:15	Pedro Berrizbeitia Universidad Simón Bolívar	On additive Properties of Multiplicative Groups on finite Index in Fields
05.11.2015 10:15	Ping Hu University of Warwick	Short induced cycles in graphs
29.10.2015 10:15	Christoph Spiegel FU Berlin	Threshold functions for systems of equations in random sets
22.10.2015 10:15	Tibor Szabó FU Berlin	Half-random Maker-Breaker games

Abstracts:

22.10.2015
Tibor Szabó (FU Berlin)
Half-random Maker-Breaker games
Abstract: We study Maker-Breaker positional games between two players, one of whom is playing randomly against an opponent with an optimal strategy. In both such scenarios, that is when Maker plays randomly and when Breaker plays randomly, we determine the sharp threshold bias of classical graph games, such as connectivity, Hamiltonicity, and minimum degree-k. The traditional, deterministic version of these games, with two optimal players playing, are known to obey the so-called probabilistic intuition. That is, the threshold bias of these games is asymptotically equal to the threshold bias of their random counterpart, where players just take edges uniformly at random. We find, that despite this remarkable agreement of the results of the deterministic and the random games, playing randomly against an optimal opponent is not a good idea: the threshold bias becomes significantly higher in favor of the clever player. An important qualitative aspect of the probabilistic intuition nevertheless carries through: for Maker to occupy a connected graph or a Hamilton cycle, the bottleneck is still the ability to achieve that there is no isolated vertex in his graph. The talk represents joint work with Jonas Groschwitz.

28.10.2015
Christoph Spiegel (FU Berlin)
Threshold functions for systems of equations in random sets
Abstract: 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 · 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 "A^m contains a non-trivial solution of M · x = 0" where A is a random set. This threshold function depends on a parameter maximized over all subsystems, a notion previously introduced by Rödl and Rucinski. 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.

05.11.2015
Ping Hu (University of Warwick)
Short induced cycles in graphs
Abstract: Let C(n) denote the maximum number of induced copies of 5-cycles in graphs on n vertices. For n large enough, we show that C(n)=abcde + C(a)+C(b)+C(c)+C(d)+C(e), where a+b+c+d+e = n and a,b,c,d,e are as equal as possible. Moreover, for n being a power of 5, we show that the unique graph on n vertices maximizing the number of induced 5-cycles is an iterated blow-up of a 5-cycle. The proof uses flag algebra computations and stability methods. Joint work with Balogh, Lidický and Pfender.

10.11.2015
Pedro Berrizbeitia (Universidad Simón Bolívar)
On additive Properties of Multiplicative Groups on finite Index in Fields
Abstract: Let m > 1 be an integer. Except for finitely many primes p, the equation x^m + y^m = t mod p has integer solutions x and y for all integer t. The problem is a classical one in Number Theory. In fact, if N_{p,t} is the number of solutions (x mod p, y mod p) of the equation, then |N_{p,t} - p| = O( p^{1/2} ). The analog problem for infinite or more general fields is the following: Let G be a multiplicative group of finite index in F*, the multiplicative group of units of the field F, what does G + G look like, in particular, when is G + G = F? The first publication on the subject appeard in 1989, when Leep and Shapiro, gave a positive answer when the index of G in F* is 3. That is, they proved that G + G = F, except for a small and short list of exceptional fields. They conjectured that the result was true in the case of index 5, for any infinite field F. They mentioned that they had not been succesfull even for F = Q, the rational numbers. In the talk we will prove that if G is of finite index in Q*, then G − G = Q, that is, every rational number is writen as the difference of two elements of G. The proof is a very nice application of the Van der Waerden Theorem on artithmetic progressions, that we will state without proof. More general results in Ramsey Theory allow to prove the same result of any infinite field, and even for some other more general rings. We will brieffly describe these more general results and consequences. We will also discuss the behaviour of G + G, of G + G + G, etc. In fact, we will scketch the solution published in 2011 of a conjecture posed in 1992 by Bergelson and Shapiro on an additive question and give Florian’s theorem on the general behaviour of G_n + G_n, for a specific sequence of subgroups of index n ∈ Q*.

19.11.2015
Olaf Parczyk (Goethe Universität Frankfurt)
Universality in random and sparse hypergraphs
Abstract: Finding spanning subgraphs is a well studied problem in random graph theory, in the case of hypergraphs less is known and it is natural to study the corresponding spanning problems for random hypergraphs. We study universality, i.e. when does an r-uniform hypergraph contain any hypergraph on n vertices and with maximum vertex degree bounded by $\Delta$? For $\mathcal{H}^{(r)}(n,p)$ we show that this holds for $p=\omega( (\ln n/n)^{ 1/ \Delta } )$ a.a.s. Furthermore we derive from explicit constructions of universal graphs due to Alon, Capalbo constructions of universal hypergraphs of size almost matching the lower bound $\Omega (n^{r-r/ \Delta})$. This is joint work with Samuel Hetterich and Yury Person.

26.11.2015
József Balogh (University of Illinois)
On Some Recent Applications of the Container Method
Abstract: I will talk about some recent applications of the container method. There are two types of applications, I present examples for both; one where it is unexpected that the method would work, the other where it is expected, but current versions of container lemmas are not applicable. Partly it is joint work with Jozsef Solymosi and Adam Wagner.

03.12.2015
Shagnik Das (FU Berlin)
The Erdős-Rothschild problem for intersecting families
Abstract: The Erdős-Rothschild problem is a twist on the typical extremal problem, asking for the structure with the maximum number of r-colourings without a monochromatic forbidden substructure. While originally phrased in the context of Turán theory, it can extend any extremal problem. Recently, there has been a great deal of interest in the Erdős-Rothschild problem for intersecting families, particularly for families of sets or vector spaces. We will present a general framework that allows us to extend these previous results to much larger, and, in some cases, optimal, choices of parameters of the families in question. This proof also applies to new settings, such as intersecting families of permutations. Joint work with Dennis Clemens and Tu(r)an Tran.

10.12.2015
Julia Wolf (University of Bristol)
Counting monochromatic structures in finite abelian groups
Abstract: In this talk we aim to determine the minimum number of monochromatic additive configurations in any 2-colouring of a finite abelian group (such as Z/pZ for p a prime). The techniques used to address this question, which include additive combinatorics and quadratic Fourier analysis, originate in quantitative approaches to Szemeredi’s theorem. Perhaps surprisingly, some of our results in the arithmetic setting have implications for a graph-theoretic problem that has been open since the 1960s.

14.01.2016
Torsten Mütze (TU Berlin)
Bipartite Kneser graphs are Hamiltonian
Abstract: For integers k>=1 and n>=2k+1, the bipartite Kneser graph H(n,k) is defined as the graph that has as vertices all k-element and all (n-k)-element subsets of {1,2,...,n}, with an edge between any two vertices (=sets) where one is a subset of the other. It has long been conjectured that all bipartite Kneser graphs have a Hamilton cycle. The special case of this conjecture concerning the Hamiltonicity of the graph H(2k+1,k) became known as the 'middle levels conjecture' or 'revolving door conjecture', and has attracted particular attention over the last 30 years. One of the motivations for tackling these problems is an even more general conjecture due to Lovasz, which asserts that in fact every connected vertex-transitive graph (as e.g. H(n,k)) has a Hamilton cycle (apart from five exceptional graphs). In this talk I present a simple and short induction proof that all bipartite Kneser graphs H(n,k) have a Hamilton cycle (assuming that H(2k+1,k) has one). This is joint work with Pascal Su (ETH Zurich).

21.01.2016
Giulia Codenotti (FU Berlin)
Kruskal-Katona and Macauley theorems in a relative setting
Abstract: A relative simplicial complex is a family of sets which is the set-theoretic difference D\G of a simplicial complex D and a subcomplex G of D. Relative simplicial complexes were introduced by Reisner and Stanley, and in a recent paper of Adiprasito and Sanyal, properties of relative simplicial complexes play a key role in solving the upper bound problem for Minkowski sums of polytopes, which asks for an upper bound on the number of k-faces of a Minkowski sum of polytopes. This has raised interest in better understanding which properties of simplicial complexes can be "relativized". One fundamental result about simplicial complexes is the Kruskal-Katona theorem, which characterizes f-vectors of simplicial complexes. I will show a simple extension of the Kruskal-Katona theorem to relative simplicial complexes, and an analogue extension for Macauley theorem [which can be interpreted as an analogue of the Kruskal-Katona theorem for multicomplexes]. This is joint work with Raman Sanyal.

28.01.2016
Christoph Spiegel (FU Berlin)
Van der Waerden Games
Abstract: 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 - 7k^(7/8)) < W*(k) < k^3 2^(k-2) where W*(k) is the least integer n so that the first player has a winning strategy.

04.02.2016
Christoph Spiegel (FU Berlin)
Van der Waerden Games - Part II
Abstract: This talk will be the direct continuation of last week's talk, for which the abstract was the following. 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 - 7k^(7/8)) < W*(k) < k^3 2^(k-2) where W*(k) is the least integer n so that the first player has a winning strategy.

11.02.2016
Mészáros Tamás (FU Berlin)
A conjecture on shattering-extremal set systems
Abstract: We say that a set system F ⊆ 2^[n] shatters a given set s ⊆ [n] if F|s = {f ∩ s : f ∈ F} = 2^s . One related notion is the VC-dimension of a set system: the size of the largest set shattered by F. The Sauer inequality states that in general, a set system F shatters at least |F| sets. A set system is called shattering-extremal if it shatters exactly |F| sets. Such families have many interesting features. Here we present several approaches to study shattering-extremal set systems together with a conjecture about the eliminability of elements from extremal families.

18.02.2016
Codruţ Grosu (FU Berlin)
A lower bound for the Towers of Hanoi game with more pegs.
Abstract: The Towers of Hanoi puzzle is played with N disks and 3 pegs. The disks are initially placed on one peg in increasing order according to size, and the goal is to move all the disks on another peg, without ever placing a larger disk on a smaller one. The solution is simple and uses a recursive algorithm for moving the disks. A well-known generalization asks for the minimum number of moves when p pegs are available. This problem is much more difficult and only recently the case p = 4 was solved by Bousch. The purpose of my talk is to present a lower bound on the number of moves needed for p ≥ 5 pegs and N disks. This lower bound is asymptotically better than the previously best known when p is fixed and N tends to infinity.

27.04.2016
Dhruv Mubayi (UI Chicago)
Recent advances using the stepping up technique.
Abstract: I will give some details of recent constructions in hypergraph Ramsey theory that settle longstanding problems in the field. These are obtained by adding some new ingredients to the stepping up method of Erdos and Hajnal that first appeared in 1965. Most of this is joint work with Andrew Suk.

04.05.2016
Katherine Staden (University of Warwick)
The Erdős-Rothschild problem on edge-colourings.
Abstract: Let $\bm{k} = (k_1,\ldots,k_s)$ be an $s$-tuple of positive integers. Given a graph $G$, how many ways are there to colour the edges of $G$ with $s$ colours so that there is no $c$-coloured copy of the complete graph on $k_c$ vertices, for any $c=1,\ldots,s$? Write $F(G;\bm{k})$ for this quantity and let $F(n;\bm{k})$ be its maximum over all graphs $G$ on $n$ vertices. What is $F(n;\bm{k})$ and which graphs $G$ attain this maximum? This problem was first considered by Erd\H{o}s and Rothschild in 1974, but it has only been solved for a very small number of non-trivial cases. In this talk I will survey the history of the problem, and will discuss some recent general results with Oleg Pikhurko (Warwick) and Zelealem Yilma (Carnegie Mellon Qatar).

12.05.2016
Tibor Szabó ( FU Berlin )
On the complexity of Ryser's Conjecture.
Abstract: Every r-uniform hypergraph has a vertex cover of size r times its matching number. Ryser's Conjecture states that if the hypergraph is also r-partite, then for a cover it is enough to take (r-1)-times the matching number many vertices. For r=2 Ryser's Conjecture reduces to Konig's Theorem, for r=3 it was proved by Aharoni by topolgical methods, and for larger r it is wide open. In a recent joint work with Abu-Khazneh, Barat, and Pokrovskiy, we argue that Ryser's Conjecture, if true, is probably difficult.

19.05.2016
Tuan Tran ( Czech Academy of Sciences )
Structure and supersturation for intersecting families.
Abstract: A k-uniform family of subsets of [n] is called intersecting if it does not contain a pair of disjoint sets. The celebrated Erdos-Ko-Rado Theorem from 1961 asserts that, provided n>2k, any such system has size at most {n-1 \choose k-1}. A natural question is how many disjoint pairs must appear in a set system of larger size. In this paper, we determine the minimum number of disjoint pairs in small k-uniform families for k=o(\sqrt{n}), thus extending a result of Das, Gan and Sudakov (2016). Our main tool is a removal lemma for families with few disjoint pairs. As another application of the removal lemma, we show that almost all k-uniform intersecting families on [n], with n>(2+o(1))k, are trivial, i.e. all k-sets share a common element. This is based on my joint work with Balogh, Das, Liu and Sharifzadeh

02.06.2016
Christian Reiher ( University of Hamburg )
A Ramsey Class for Steiner Systems.
Abstract: We construct a Ramsey class whose objects are Steiner systems. In contrast to the situation with general $r$-uniform hypergraphs, it turns out that simply putting linear orders on their sets of vertices is not enough for this purpose: we also have to strengthen the notion of subobjects used from ``induced subsystems'' to something we call ``strongly induced subsystems''. Moreover we study the Ramsey properties of other classes of Steiner systems obtained from this class by either forgetting the order or by working with the usual notion of subsystems. This leads to an interesting induced Ramsey theorem in which {\it designs} get coloured. This is joint work with Vindya Bhat, Jaroslav Ne\v{s}et\v{r}il, and Vojt\v{e}ch R\"{o}dl.

23.06.2016
Dániel Korándi (ETH Zürich)
Saturation in random graphs.
Abstract: A graph H is K_s-saturated if it is a maximal K_s-free graph, i.e., H contains no clique on s vertices, but the addition of any missing edge creates one. The minimum number of edges in a K_s-saturated graph was determined over 50 years ago by Zykov and independently by Erdős, Hajnal and Moon. In this talk, we consider the random analog of this problem: minimizing the number of edges in a maximal K_s-free subgraph of the Erdős-Rényi random graph G(n,p). We give asymptotically tight estimates on this minimum, and also provide exact bounds for the related notion of weak saturation in random graphs. Joint work with Benny Sudakov.

29.06.2016
Benny Sudakov (ETH Zürich)
Equiangular lines and spherical codes in Euclidean spaces.
Abstract: A set of lines in R^d is called equiangular if the angles between any two of them are the same. The problem of estimating the size of the maximum family of equiangular lines has had a long history since late 1940's. A closely related notion is that of a spherical code, which is a collection C of unit vectors in Rd such that x \cdot y \in L for any distinct x,y in C and some set of real numbers L. Spherical codes have been extensively studied since their introduction in the 1970's by Delsarte, Goethals and Seidel. Despite a lot of attention in the last forty years, there are still many open interesting questions about equiangular lines and spherical codes. In this talk we report recent progress on some of them. Joint work with I. Balla, F. Drexler and P. Keevash.

07.07.2016
Anita Liebenau (Monash University)
Ramsey equivalence of $K_n$ and $K_n + K_{n−1}$.
Abstract:Szab\’o, Zumstein, and Z\”urcher proved in 2010 that, for $n\geq 4$, the complete graph $K_n$ is Ramsey equivalent to $K_n+K_{n-2}$, the graph formed by taking the disjoint union of a copy of $K_n$ and a copy of $K_{n-2}$. In fact, they proved that one can add {\em many} disjoint copies of $K_{n-2}$ to $K_n$, and the resulting graph is still Ramsey equivalent to $K_n$. The situation is quite different for $K_{n-1}$: Fox, Grinshpun, Liebenau, Person, and Szab\’o proved in 2014 that $K_n$ is {\em not} Ramsey equivalent to the graph $K_n + 2K_{n-1}$, the graph containing a copy of $K_n$ and two copies of $K_{n-1}$. Nevertheless, it was conjectured in both papers that $K_n$ and $K_n + K_{n−1}$ are Ramsey equivalent for $n\geq 4$. We prove this conjecture. This is joint work with Thomas Bloom. .

13.07.2016
Boris Bukh (Carnegie Mellon University)
One-sided epsilon-approximants .
Abstract: Two common approximation notions in discrete geometry are ε-nets and ε-approximants. Of the two, ε-approximants are stronger. For the family of convex sets, small ε-nets exist while small ε-approximants unfortunately do not. In this talk, we introduce a new notion "one-sided ε-approximants", which is of intermediate strength, and prove that small one-sided ε-approximants do exist. The proof is based on a (modification of) the regularity lemma for words by Axaenovich--Person--Puzynina. Joint work with Gabriel Nivasch.