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.

DateSpeakerTitle
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

07.12.2017
Lutz Warnke
(Georgia Institute of Technology)

Paking nearly optimal Ramsey R(3,t) graphs

14.12.2017
Martin Skrodzki
(FU Berlin)

[Title]

11.01.2018
Torsten Muetze
(TU Berlin)

[Title]

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.

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.