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

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 
07.12.2017 
Lutz Warnke (Georgia Institute of Technology) 

14.12.2017 
Martin Skrodzki (FU Berlin) 

11.01.2018 
Torsten Muetze (TU Berlin) 
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. 
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. 