2017/2018
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 

19.07.2018  Daniele Bartoli (University of Perugia) 
Permutation polynomials over finite fields 
12.07.2018  Jeroen Schillewaert (University of Auckland, NZ) 
Combinatorial methods in finite geometry 
05.07.2018  Necati Alp Muyesser (CMU) 
Ramseytype results for balanced graphs 
28.06.2018  Alexey Pokrovskiy (ETH Zürich) 
Ryser's Conjecture & diameter 
21.06.2018  Benny Sudakov (ETH Zürich) 
Rainbow structures, Latin squares & graph decompositions 
13.06.2018  John Bamberg (UWA Perth) 
Hemisystemlike objects in finite geometry 
30.05.2018  Malte Renken (FU Berlin) 
Finding Disjoint Connecting Subgraphs in Surfaceembedded Graph 
24.05.2018  Anurag Bishnoi (FU Berlin) 
A generalization of ChevalleyWarning and AxKatz via polynomial substitutions 
09.05.2018  Milos Stojakovic (University of Novi Sad) 
Semirandom graph process 
26.04.2018  Patrick Morris (FU Berlin) 
Tilings in randomly perturbed hypergraphs 
25.04.2018  Shagnik Das (FU Berlin) 
Colourings without monochromatic chains 
19.04.2018  Ander Lamaison (FU Berlin) 
Ramsey density of infinite paths 
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. 
19.04.2018 
Ander Lamaison (FU Berlin) 
Ramsey density of infinite paths 
Abstract: In a twocolouring of the edges of the complete graph on the natural numbers, what is the densest monochromatic infinite path that we can always find? We measure the density of a path by the upper asymptotic density of its vertex set. This question was first studied by Erdös and Galvin, who proved that the best density is between 2/3 and 8/9. In this talk we settle this question by proving that we can always find a monochromatic path of upper density at least (12+sqrt(8))/17=0.87226…, and constructing a twocolouring in which no denser path exists. This represents joint work with Jan Corsten, Louis DeBiasio and Richard Lang. 
25.04.2018 

Shagnik Das (FU Berlin) 
Colourings without monochromatic chains 
Abstract: In 1974, Erdős and Rothschild introduced a new kind of extremal problem, asking which nvertex graph has the maximum number of monochromatictrianglefree red/blue edgecolourings. While this original problem strengthens Mantel’s theorem, recent years have witnessed the study of the ErdősRothschild extension of several classic combinatorial theorems. In this talk, we seek the ErdősRothschild extension of Sperner’s Theorem. More precisely, we search for the set families in 2^{[n]} with the most monochromatickchainfree rcolourings. Time and interest permitting, we shall present some results, sketch some proofs, and offer many open problems.
This is joint work with Roman Glebov, Benny Sudakov and Tuan Tran. 
26.04.2018 

Patrick Morris (FU Berlin) 
Tilings in randomly peturbed hypergraphs 
Abstract: In 2003, Bohman, Frieze and Martin introduced a random graph model called the perturbed model. Here we start with some $\alpha>0$ and an arbitrary graph $G$ of minimum degree $\alpha n$. We are then interested in the threshold probability $p=p(n)$ for which $G \cup G(n,p)$ satisfies certain properties. That is, for a certain property, for example Hamiltonicity, we can ask what is the minimum probability $p(n)$, such that for \emph{any} $n$vertex graph $G$ of minimum degree $\alpha n$, $G \cup G(n,p)$ has this property with high probability. This model has been well studied and the threshold probability has been established for various properties. One key property is the notion of having a $H$tiling for some fixed graph $H$. By this, we mean a union of disjoint copies of $H$ in $G\cup G(n,p)$ that covers every vertex exactly once. This generalisation of a perfect matching is fundamental and was studied in the setting of perturbed dense graphs by Balogh, Treglown and Wagner in 2017. In this talk, we look to extend this problem to the setting of hypergraphs. This is work in progress and joint with Wiebke Bendenknecht, Jie Han, Yoshiharu Kohayakawa and Guilherme Mota. 
09.05.2018 

Milos Stojakovic (University of Novi Sad) 
Semirandom graph process 
Abstract: We introduce and study a novel semirandom multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to v. For various natural monotone increasing graph properties P, we give tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies P. Along the way, we show that the process is general enough to approximate (using suitable strategies) several wellstudied random graph models. Joint work with: Omri BenEliezer, Dan Hefetz, Gal Kronenberg, Olaf Parczyk and Clara Shikhelman. 
30.05.2018 

Malte Renken (FU Berlin) 
Finding Disjoint Connecting Subgraphs in Surfaceembedded Graph 
Abstract: Given a graph $G$, a set $T \subseteq V(G)$ of terminal vertices and a partition of $T$ into blocks, the problem "Disjoint Connecting Subgraphs" is to find a set of vertexdisjoint subgraphs of G, each covering exactly one block. While NPhard in general, Robertson and Seymour showed that the problem is solvable in polynomial time for any fixed size of $T$. Generalizing a result of Reed, we give an $O(n \log(n))$ algorithm for when $G$ is embedded into an arbitrary but fixed surface. 
13.06.2018 

John Bamberg (UWA Perth) 
Hemisystem like objects in finite geometry 
Abstract: Beniamino Segre showed in his 1965 manuscript 'Forme e geometrie hermitiane, con particolare riguardo al caso finito' that there is no way to partition the points of the Hermitian surface H(3,q^2) into lines, when q is odd. Moreover, Segre showed that if there is an mcover of H(3,q^2), a set of lines covering each point m times, then m=(q+1)/2; half the number of lines on a point. Such a configuration of lines is known as a hemisystem and they give rise to interesting combinatorial objects such as partial quadrangles, strongly regular graphs, and imprimitive cometric Qantipodal association schemes. This talk will be on developments in the field of hemisystems of polar spaces and regular near polygons and their connections to other interesting combinatorial objects. No background in finite geometry will be assumed. 
21.06.2018 

Benny Sudakov (ETH Zurich) 
Rainbow structures, Latin squares & graph decompositions 
Abstract: A subgraph of an edgecoloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares. Since then rainbow structures were the focus of extensive research and found applications in design theory and graph decompositions. In this talk we discuss how probabilistic reasoning can be used to attack several old problems in this area. In particular we show that well known conjectures of Ryser, Hahn, Ringel, GrahamSloane and BrualdiHollingsworth hold asymptotically. Based on joint works with Alon, Montgomery, and Pokrovskiy. 
28.06.2018 

Alexey Pokrovskiy (ETH Zurich) 
Ryser's Conjecture & diameter 
Abstract: Ryser conjectured that the vertices of every redgecoloured graph with independence number i can be covered be (r  1)i monochromatic trees. Recently Milicevic conjectured that moreover one can ensure that these trees have bounded diameter. We'll show that the two conjectures are equivalent. As a corollary one obtains new results about Milicevic's Conjecture. 
05.07.2018 

Necati Alp Muyesser (CMU) 
Ramseytype results for balanced graphs 
Abstract: Consider G, a 2coloring of a complete graph on n vertices, where both color classes have at least \ep fraction of all the edges. Fix some graph H, together with a 2coloring of its edges. By H^c, we denote the same graph with the colors switched. How large does n have to be so that G necessarily contains one of H or H^c as a subgraph? Call the smallest such integer, if it exists, R_\ep(H). We completely characterize the H for which R_\ep(H) is finite, discuss some quantitative bounds, and consider some related problems. Based on joint works with Matthew Bowen and Ander Lamaison. 
12.07.2018 

Jeroen Schillewaert (University of Auckland, NZ) 
Combinatorial methods in finite geometry 
Abstract: I will discuss a few different combinatorial techniques to study and characterise special classes of incidence structures (ovoids, spreads, maximal arcs,...) in finite geometry 
19.07.2018 

Daniele Bartoli (University of Perugia) 
Permutation polynomials over finite fields 
Abstract: Let q = p^h be a prime power. A polynomial f(x) in Fq[x] is a permutation polynomial (PP) if it is a bijection of the finite field Fq into itself. On the one hand, each permutation of Fq can be expressed as a polynomial over Fq. On the other hand, particular, simple structures or additional extraordinary properties are usually required by applications of PPs in other areas of mathematics and engineering, such as cryptography, coding theory, or combinatorial designs. Permutation polynomials meeting these criteria are usually difficult to find. A standard approach to the problem of deciding whether a polynomial f(x) is a PP is the investigation of the plane algebraic curve Cf : (f(x) − f(y))/(x − y) = 0; in fact, f is a PP over Fq if and only if Cf has no Fqrational point (a, b) with a != b. In this talk, we will see applications of the above criterion to classes of permutation polynomials, complete permutation polynomials, exceptional polynomials, Carlitz rank problems, the Carlitz conjecture. 