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.

DateSpeakerTitle
14.02.2018 Andrei Asinowski
(FU Berlin)
Enumeration of lattice paths with forbidden patterns
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 tree-width
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)

Old and new results on extremal generalized polygons

29.11.2017

Ander Lamaison
(FU Berlin)

The random strategy in Maker-Breakers
16.11.2017
Patrick Morris
(FU Berlin)

Random Steiner Triple systems

09.11.2017
Anurag Bishnoi
(FU Berlin)

Spectral methods in extremal combinatorics

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 vertex-disjoint 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 NP-complete.

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 so-called 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 Maker-Breaker

Abstract: We consider biased Maker-Breaker 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 point-line 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 triangle-free 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 edge-disjoint collection $(G_i)_i$ of $n$-vertex graphs $G_i \subseteq K_n$ such that (a)~each $G_i$ is triangle-free 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 semi-random (i.e., R\"{o}dl nibble type) variation of the triangle-free process. As an application, we prove a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szab\'{o} (concerning a Ramsey-type 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 polynomial-time 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 co-prime 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 well-studied 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 k-element 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^{k-6}} 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 tree-width

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 tree-width have bounded boolean dimension. This stays in contrast with the fact that there are posets with cover graphs of tree-width 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$-edge-colored 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.

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.
We extend and refine the study of Banderier and Flajolet by considering lattice paths that avoid a "pattern" -- a fixed word p. In many cases we obtain expressions that generalize those from the work by Banderier and Flajolet. Our results unify and include numerous earlier results on lattice paths with forbidden patterns (for example, UDU-avoiding Dyck paths, UHD-avoiding Motzkin paths, etc.) Our main tool is a combination of finite automata machinery with a suitable extention of the kernel method.

A joint work with A. Bacher, C. Banderier and B. Gittenberger.