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

28.02.2018  Penny Haxell (University of Waterloo) 
Chromatic index of random multigraphs 
14.02.2018  Andrei Asinowski (FU Berlin) 
Enumeration of lattice paths with forbidden patterns 
07.02.2018  Anurag Bishnoi (FU Berlin) 
Zeros of a polynomial in a finite grid 
01.02.2018  Tibor Szabó (FU Berlin) 
Exploring the projective norm graphs 
24.01.2018  Dániel Korándi (EPFL) 
Rainbow saturation and graph capacities 
18.01.2018  Tamás Mészáros (FU Berlin) 
Boolean dimension and treewidth 
11.01.2018  Torsten Muetze (TU Berlin) 
Sparse Kneser graphs are Hamiltonian 
21.12.2017  Simona Boyadzhiyska (FU Berlin) 
Interval orders with restrictions on the interval lengths 
20.12.2017  Christoph Spiegel (UPC Barcelona) 
On a question of Sárkozy and Sós 
14.12.2017  Martin Skrodzki (FU Berlin) 
Combinatorial and Asymptotical Results on the Neighborhood Grid 
07.12.2017  Lutz Warnke (Georgia Institute of Technology) 
Paking nearly optimal Ramsey R(3,t) graphs 
06.12.2017 
Bart De Bruyn (Ghent University) 

29.11.2017 
Ander Lamaison 
The random strategy in MakerBreakers 
16.11.2017 
Patrick Morris (FU Berlin) 

09.11.2017 
Anurag Bishnoi (FU Berlin) 

25.10.2017 
Andrew Treglown (Birmingham) 
The complexity of perfect matchings and packings in dense hypergraphs 
25.10.2017 

Andrew Treglown (Birmingham) 
The complexity of perfect matchings and packings in dense hypergraphs 
Abstract: Given two $k$graphs $H$ and $F$, a perfect $F$packing in $H$ is a collection of vertexdisjoint copies of $F$ in $H$ which together cover all the vertices in $H$. In the case when $F$ is a single edge, a perfect $F$packing is simply a perfect matching. For a given fixed $F$, it is generally the case that the decision problem whether an $n$vertex $k$graph $H$ contains a perfect $F$packing is NPcomplete. In this talk we describe a general tool which can be used to determine classes of (hyper)graphs for which the corresponding decision problem for perfect $F$packings is polynomial time solvable. We then give applications of this tool. For example, we give a minimum $\ell$degree condition for which it is polynomial time solvable to determine whether a $k$graph satisfying this condition has a perfect matching (partially resolving a conjecture of Keevash, Knox and Mycroft). We also answer a question of Yuster concerning perfect $F$packings in graphs. This is joint work with Jie Han (Sao Paulo). 
09.11.2017 
Anurag Bishnoi (FU berlin) 
Spectral methods in extremal combinatorics 
Abstract: I will introduce an eigenvalue technique from graph theory (the socalled expander mixing lemma) and discuss some of its recent applications in the problem of finding the largest minimal blocking set (vertex cover), and the cage problem. 
16.11.2017 
Patrick Morris (FU berlin) 
Random Steiner Triple Systems 
Abstract: We look at a recent method of Matthew Kwan comparing a uniformly random Steiner triple system to the outcome of the triangle removal process. Using this method, we show the asymptotic almost sure existence of (linearly many disjoint) perfect matchings in random Steiner triple systems. This talk is based on work from my Masters thesis which presented the work of Kwan. 
29.11.2017 
Ander Lamaison (FU berlin) 
The random strategy in MakerBreaker 
Abstract: We consider biased MakerBreaker games in graphs. Bednarska and Luczak proved that, if Maker’s goal is to create a copy of a fixed graph G, then playing randomly is close to being optimal for Maker. In this talk we will look at some related families of games and study the gap between the random strategy and the optimal strategy. This talk is based on my Master’s thesis. 
06.12.2017 
Bart De Bruyn (Ghent University) 
Old and new results on extremal generalized polygons 
Abstract: A generalized $n$gon with $n \geq 3$ is a pointline geometry whose incidence graph has diameter $n$ and (maximal possible) girth $2n$. Such a generalized $n$gon is said to have order $(s,t)$ if every line is incident with precisely $s+1$ points and if every point is incident with exactly $t+1$ lines. If $\mathcal{S}$ is a generalized $2d$gon of order $(s,t)$ with $d \in \{ 2,3,4 \}$ and $s > 1$, then an inequality due to Haemers and Roos states that $t \leq s^3$ in case $\mathcal{S}$ is a generalized hexagon, and inequalities due to Higman state that $t \leq s^2$ in case $\mathcal{S}$ is a generalized quadrangle or octagon. In case $t$ attains its maximal possible value, the generalized polygon $\mathcal{S}$ is called {\em extremal}. In my talk, I will give a proof of the Higman inequality $t \leq s^2$ for generalized quadrangles. I will also discuss combinatorial characterisations of the extremal generalized polygons. Some of these characterisation results are very recent. 
07.12.2017 
Lutz Warnke (Georgia Institute of Technology) 
Packing near optimal Ramsey R(3,t) graphs 
Abstract: In 1995 Kim famously proved the Ramsey bound~$R(3,t) \ge c t^2/\log t$ by constructing an $n$vertex graph that is trianglefree and has independence number at most~$C \sqrt{n \log n}$. We extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graph~$K_n$ into a packing of such nearly optimal Ramsey~$R(3,t)$ graphs. More precisely, for any $\epsilon>0$ we find an edgedisjoint collection $(G_i)_i$ of $n$vertex graphs $G_i \subseteq K_n$ such that (a)~each $G_i$ is trianglefree and has independence number at most $C_\epsilon \sqrt{n \log n}$, and (b)~the union of all the $G_i$ contains at least $(1\epsilon)\binom{n}{2}$ edges. Our algorithmic proof proceeds by sequentially choosing the graphs~$G_i$ via a semirandom (i.e., R\"{o}dl nibble type) variation of the trianglefree process. As an application, we prove a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szab\'{o} (concerning a Ramseytype parameter introduced by Burr, Erd\H{o}s, Lov\'asz in 1976). Namely, denoting by~$s_r(H)$ the smallest minimum degree of $r$Ramsey minimal graphs for~$H$, we close the existing logarithmic gap for~$H=K_3$ and establish that~$s_r(K_3) = \Theta(r^2 \log r)$. Joint work with He Guo. 
14.12.2017 
Martin Skrodzki (FU Berlin) 
Combinatorial and Asymptotical Results on the Neighborhood Grid 
Abstract: In 2009, Joselli et al introduced the Neighborhood Grid data structure for fast computation of neighborhood estimates in point clouds. Even though the data structure has been used in several applications and shown to be practically relevant, it is theoretically not yet well understood. The purpose of this talk is to present a polynomialtime algorithm to build the data structure. Furthermore, it is investigated whether the presented algorithm is optimal. This investigations leads to several combinatorial questions for which partial results are given. 
20.12.2017 
Christoph Spiegel (UPC Barcelona) 
On a question of Sárkozy and Sós 
Abstract: Sárkozy and Sós posed the following question: for which (k_1, …, k_d) does there exist some infinite sequence of positive integers A such that the function r(A,n) counting the number of solutions of k_1 a_1 + … + k_d a_d = n becomes constant? Moser observed that in the case (1,k) such a sequence exists if and only if k > 1. Cilleruelo and Rue settled the case d = 2, showing that for k_1, k_2 > 1 no such sequence can exist. Here we present some progress towards the case of general d, showing that for pairwise coprime k_1, …, k_d > 1 such a sequence can also not exist. 
21.12.2017 
Simona Boyadzhiyska (FU Berlin) 
Interval orders with restrictions on the interval lengths 
Abstract: A poset P = (X,<) has an interval representation if we can assign a closed real interval to each x in X so that x<y in P if and only if the interval of x lies completely to the left of the interval of y; if P has an interval representation, then P is called an interval order. Interval orders have been characterized both structurally and algorithmically, and a natural next question to ask is: what classes of interval orders arise if we impose restrictions on the permissible interval lengths? The most wellstudied such class is that of the unit interval orders: interval orders that have representations in which all intervals have unit length. In this talk, we will consider intermediate classes between the two extremes of interval orders and unit interval orders. We will use weighted digraph models to characterize some of these classes. This talk is based on joint work with Ann Trenk and Garth Isaak. 
11.01.2018 
Torsten Muetze (TU Berlin) 
Sparse Kneser graphs are Hamiltonian 
Abstract: For integers k>=1 and n>=2k+1, the Kneser graph K(n,k) is the graph whose vertices are the kelement subsets of {1,...,n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k+1,k) are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k>=3, the odd graph K(2k+1,k) has a Hamilton cycle. This and a known conditional result due to Johnson imply that all Kneser graphs of the form K(2k+2^a,k) with k>=3 and a>=0 have a Hamilton cycle. We also prove that K(2k+1,k) has at least 2^{2^{k6}} distinct Hamilton cycles for k>=6. Our proofs are based on a reduction of the Hamiltonicity problem in the odd graph to the problem of finding a spanning tree in a suitably defined hypergraph on Dyck words. This is joint work with Jerri Nummenpalo and Bartosz Walczak. 
18.01.2018 
Tamás Mészáros (FU Berlin) 
Boolean dimension and treewidth 
Abstract: The dimension of a partially ordered set P is an extensively studied parameter. Small dimension allows succinct encoding. Indeed if P has dimension d, then to know whether x < y in P it is enough to check whether x < y in each of the d linear extensions of a witnessing realizer. Focusing on the encoding aspect Nešetřil and Pudlák defined the boolean dimension so that P has boolean dimension at most d if it is possible to decide whether x < y in P by looking at the relative position of x and y in only d permutations of the elements of P. The main result presented in this talk is that posets with cover graphs of bounded treewidth have bounded boolean dimension. This stays in contrast with the fact that there are posets with cover graphs of treewidth three and arbitrarily large dimension. This is joint work with Stefan Felsner (TU Berlin) and Piotr Micek (Jagiellonian University Krakow). 
24.01.2018 
Dániel Korándi (EPFL) 
Rainbow saturation and graph capacities 
Abstract: The $t$colored rainbow saturation number $\rsat_t(n,F)$ is the minimum size of a $t$edgecolored graph on $n$ vertices that contains no rainbow copy of $F$, but the addition of any missing edge in any color creates such a rainbow copy. Barrus, Ferrara, Vandenbussche and Wenger conjectured that $\rsat_t(n,K_s) = \Theta(n\log n)$ for every $s\ge 3$ and $t\ge \binom{s}{2}$. In this talk I will explain how this problem is related to the Shannon capacity of a certain family of cliques, and use this connection to prove the conjecture in a strong sense, asymptotically determining the rainbow saturation number for triangles. 
01.02.2018 
Tibor Szabó (FU Berlin) 
Exploring the projective norm graphs 
Abstract: The projective norm graphs $NG(t,q)$ provide tight constructions for the Turán number of complete bipartite graphs $K_{t,s}$ with $s > t!$. In this talk we discuss their automorphism group and explore their small subgraphs. In particular we count their 3degenerate subgraphs and prove that $NG(4, q)$ does contain (many) $K_{4,6}$. Some of these result also extend the work of Alon and Shikhelman on generalized Turán numbers. We also give a new, more elementary proof for the $K_{4,7}$freeness of $NG(4,q)$. The talk represents joint work with Tomas Bayer, Tamás Mészáros, and Lajos Rónyai. 
07.02.2018 
Anurag Bishnoi (FU Berlin) 
Zeros of a polynomial in a finite grid 
Abstract: A finite grid is a set of the form A = A_1 \times \cdots \times A_n \subseteq \mathbb{F}^n where \mathbb{F} is a field and all A_i's are finite subsets of \mathbb{F}. We will look at some of the fundamental (and elementary) results related to how a multivariate polynomial ``interacts'' with a finite grid. I will prove some of these results and explain some of the interesting applications to number theory, combinatorics and finite geometry. Moreover, I will talk about my result on estimating the number of zeros of a polynomial in a finite grid given its total degree and bounds on its degrees in each variable, which is a generalisation of the AlonFüredi theorem from 1993. This talk is based on my joint work with Pete L. Clark, Aditya Potukuchi and John R. Schmitt. 
14.02.2018 
Andrei Asinowski (FU Berlin) 
Enumeration of lattice paths with forbidden patterns 
Abstract: A ("directed") lattice path is a word (a_1, ..., a_n) over an alphabet S  a prechosen set of integer numbers. It is visualized as a polygonal line which starts in the origin and consists of the vectors (1, a_i), i=1..n, appended to each other. In 2002, Banderier and Flajolet developed a systematic study of lattice paths by means of analytic combinatorics. In particular, they found general expressions for generating functions for several classes of lattice paths ("walks", "bridges", "meanders", and "excursions") over S. A joint work with A. Bacher, C. Banderier and B. Gittenberger. 
28.02.2018 
Penny Haxell (University of Waterloo) 
Chromatic index of random multigraphs 
Abstract: Let $G$ be a loopless multigraph with maximum degree $d$. It is clear that $d$ is a lower bound for the chromatic index of $G$ (the smallest $k$ such that $E(G)$ can be partitioned into $k$ matchings). A longstanding conjecture due to Goldberg and (independently) Seymour states that the chromatic index of $G$ takes one of only three possible values: $d$, $d+1$ or a certain other parameter of $G$, that is closely related to the fractional chromatic index of $G$ (and is also a natural lower bound for the chromatic index). Here we prove this conjecture for random multigraphs. In fact we prove the stronger statement that the value $d+1$ is not necessary for the random case. We will discuss various graph theoretical tools used in the proof, in particular the method of Tashkinov trees (which has been a key component of much of the progress on this conjecture to date). This represents joint work with Michael Krivelevich and Gal Kronenberg. 