# Research Seminar on Current Topics of Logic and Algorithmic Graph Theory

Welcome on the webpage of the LaS research seminar!If you want to give a talk, contact us. To reveive our annoucements, you can subscribe to our mailing list.

Summer term 2019

Wednesday 06.03 at 14:00 in room 716

Sebastian Wiederrecht
TU Berlin

A graph G is called matching covered if it is connected and every edge is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition that can be considered a generalisation of directed treewidth. We show that the perfect matching width of every bipartite matching covered graph is within a factor of 2 of the perfect matching width of its braces. Moreover, we give characterisations for braces of perfect matching width in terms of edge maximal graphs similar to k-trees for undirected treewidth and elimination orderings. The latter allows us to identify braces of perfect matching width 2 in polynomial time and provides an algorithm to construct an optimal decomposition.

This is joint work with Archontia C. Giannopoulou and Meike Hatzel.

This is joint work with Archontia C. Giannopoulou and Meike Hatzel.

Wednesday 20.02 at 13:00 in room 716

Jean-Florent Raymond
TU Berlin

In 1990, Thomas proved that every graph admits a tree decomposition of minimum width that additionally satisfies a certain connectivity condition called leanness [A Menger-like property of tree-width: The finite case. Journal of Combinatorial Theory, Series B, 48(1):67 – 76, 1990]. This result had many uses and has been extended to several other decompositions. On the other hand, tree-cut decompositions are graph decompositions that have been introduced by Wollan as a possible edge-version of tree decompositions and that behave nicely with respect to graph immersions [The structure of graphs not admitting a fixed immersion. Journal of Combinatorial Theory, Series B, 110:47 – 66, 2015].

In this seminar, I will talk about leanness for tree-cut decompositions and present recent results obtained jointly with Archontia Giannopoulou, O-joung Kwon, and Dimitrios Thilikos.

In this seminar, I will talk about leanness for tree-cut decompositions and present recent results obtained jointly with Archontia Giannopoulou, O-joung Kwon, and Dimitrios Thilikos.

The Directed Tangle Decomposition Lemma

Wednesday 06.02 at 14:00 in room 716

Stephan Kreutzer
TU Berlin

The canonical decomposition theorem for undirected graphs is another of the main steps in the proof of the undirected structure theorem. Informally it says that any graph has a tree decomposition distinguishing its maximal tangles, or somewhat more formally, it has a tree decomposition such that for any maximal tangle in the graph there is a unique node of the decomposition whose bag contains the tangle and any pair of distinguishable tangles is contained in different bags of the decomposition. In the statement of the structure theorem (large clique minor, small tree width or a tree decomposition into pieces almost embeddable on a surface into which the graph itself does not embed) this lemma is an important part of obtaining the claimed tree decomposition into almost embeddable pieces.

In this talk I will speak about the directed version of this theorem. Note that this is a cakeless theorem.

In this talk I will speak about the directed version of this theorem. Note that this is a cakeless theorem.

The Directed Flat Wall Theorem

Wednesday 30.01 at 14:00 in room 716

Archontia Giannopoulou
TU Berlin

At the core of the Robertson-Seymour theory of graph minors lies a powerful structure theorem which captures, for any fixed graph H, the common structural features of all the graphs not containing H as a minor. An important step toward this structure theorem is the flat wall theorem, which has a lot of algorithmic applications (for example, the minor-testing and the disjoint paths problem with fixed number terminals). In this talk, we discuss the proof of the "directed" analogue of the flat wall theorem. Our result builds on the recent "directed" grid theorem by Kawarabayashi and Kreutzer.

Joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon.

Joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon.

The Infinite Lucchesi-Younger Conjecture

Wednesday 23.01 at 14:00 in room 716

Karl Heuer
TU Berlin

Lucchesi and Younger proved the following min-max theorem for digraphs: For any weakly connected finite digraph D the maximum number of disjoint dicuts of D, i.e., cuts of D all whose edges are directed to one common side of the cut, equals the minimum size of an edge set which intersects all dicuts of D.

In this talk we shall look at a new and open conjecture stating a structural extension to infinite digraphs of this theorem in an Erdős-Menger-like way. We shall discuss special cases for which the conjecture is verified, and a reduction of the conjecture to countable digraphs.

Based on joint work with J. Pascal Gollin.

In this talk we shall look at a new and open conjecture stating a structural extension to infinite digraphs of this theorem in an Erdős-Menger-like way. We shall discuss special cases for which the conjecture is verified, and a reduction of the conjecture to countable digraphs.

Based on joint work with J. Pascal Gollin.

Winter term 2018/2019

Wednesday 12.09 at 14:00 in room 716

Adrian Alic and Felix Herron
TU Berlin

Wednesday 10.10 at 14:00 in room 716

Jean-Florent Raymond
TU Berlin

Wednesday 31.10 at 14:00 in room 716

Jean-Florent Raymond
TU Berlin

Summer term 2018

Wednesday 09.05 at 13:00 in room 716

Nishad Kothari
University of Vienna

Wednesday 23.05 at 13:00 in room 716

Marcelo Garlet Millani
TU Berlin

Wednesday 13.06 at 14:00 in room 716

Jakub Gajarsky
TU Berlin

Wednesday 22.08 at 14:00 in room 716

Sebastian Wiederrecht
TU Berlin

Winter term 2017/18

27 October, 2017 / 02:00 p.m. / room TEL 716

Prof. Dr. Daniel Král
University of Warwick

Summer term 2017

Wednesday, 1st of March, 2017, 1:00 p.m., room TEL 716

Lucas Heimberg

Wednesday, 8th of March, 2017, 1:00 p.m., room TEL 716

Jean-Florent Raymond

Winter term 2016/17

Wednesday, 9th of November, 14:00 - 16:00 room TEL 716

Dr. Roman Rabinovich
Technische Universität Berlin

Wednesday, 16th of November, 14:00 - 16:00 room TEL 716

Prof. Dr. Stephan Kreutzer
Technische Universität Berlin

TBA

Wednesday, 23rd of November, 14:00 - 16:00 room TEL 716

Dr. Saeed Akhoondian Amiri
Technische Universität Berlin

TBA

Wednesday, 30th of November, 14:00 - 16:00 room TEL 716

Dr. Sebastian Siebertz
Technische Universität Berlin

Wednesday, 7th of December, 2016, 1:00 p.m., room TEL 716

Dr. Saeed Akhoondian Amiri
Technische Universität Berlin

Summer term 2016

Research Colloquium on Current Topics in Logic and Graph Theory

Wednesday, 10:00 - 12:00 room TEL 716 (in irregular intervals, we will give concrete announcements)

Prof. Dr. Stephan Kreutzer
Technische Universität Berlin

Wednesday, 20th July 2016, 2:00 p.m., room TEL 716

Dr. Eun Jung Kim
Texas A & M University

Wednesday, 29th June 2016, 1:00 p.m., room TEL 716

Daniel A. Quiroz
London School of Economics and Political Science

Thursday, 30th June 2016, 1:00 p.m., room TEL 716

Prof. Jan van den Heuvel
London School of Economics and Political Science

Winter term 2014/15

Friday, 5th December 2014, 1:00 p.m., room TEL 716

Dr. Roman Rabinovich
Technische Universität Berlin

Wednesday, 10th December 2014, 1:15 p.m., room TEL 716

Prof. Dr. Stephan Kreutzer
Technische Universität Berlin

Wednesday, 10th December 2014, 2:30 p.m., room TEL 716

Viktor Engelmann
Technische Universität Berlin

Winter term 2013/14

Friday, 8th November 2013, 10:00 a.m., room TEL 716

Technische Universität Berlin

Winter term 2012/13

Friday, 19th October 2012, 11:00 a.m., room TEL 716

Humboldt-Universität zu Berlin

Friday, 26th Oktober 2012, 11:00 a.m., room TEL 716

Technische Universität Berlin

Friday, 9th November 2012, 11:00 a.m., room TEL 716

University of Oxford

Friday, 23th November 2012, 11:00 a.m., room TEL 716

University of Cambridge

Friday, 7th Dezember 2012, 11:00 a.m., room TEL 716

Humboldt Universiät zu Berlin

Friday, 8th February 2013, 11:00 a.m., room TEL 716

Technische Universität Berlin

Monday, 11th March 2013, 1:00 p.m., room TEL 716

Technische Universität Berlin

Tuesday, 16th July 2013, 10:00 a.m., room TEL 716

Goethe-Universiät Frankfurt am Main

Summer term 2012

Monday, 27th August 2012, 2:00 pm, room TEL 512

Technische Universität Wien

Monday, 13th August 2012, 2:00 pm, room TEL 512

Technische Universität Berlin

Tuesday, 3rd July 2012, 1:00 pm, room TEL 512

Karlsuniversität Prag

Friday, 29th June 2012, 9:00 am, room TEL 512

Technische Universität Berlin

Tuesday, 12th June 2012, 9:00 am, room TEL 512

Technische Universität Berlin