Online talk: ‪Stephan Kreutzer‬

Monday, January 11, 3pm ET (8pm GMT, 9am Tue NZDT)
Stephan Kreutzer, TU Berlin
Directed tangles

Abstract:

A tangle in a graph $G$ is a consistent orientation of all low-order separations of $G$.
In this way, tangles define the “highly connected” pieces of the graph.

Robertson and Seymour introduced the concept of tangles as part of their graph minor series and proved that the maximal tangles in a graph form a tree structure. More formally, every graph has a tree-decomposition whose pieces correspond to its maximal tangles. This tangle decomposition theorem is one of the essential steps in their proof of the graph minor theorem and has also found many other applications.

Recently, we defined “directed tangles”, the analogue of tangles for digraphs, and showed that again every digraph can be decomposed into a tree of its maximal tangles.

In this talk I will introduce directed tangles and present a proof of the main directed tangle decomposition theorem. I will also focus on the differences between the directed and undirected case and sketch potential applications of the directed tangle decomposition theorem.

The talk is based on joint with with Archontia Giannopoulou, Ken-ichi Kawarabayashi, and O-Joung Kwon.

This site uses Akismet to reduce spam. Learn how your comment data is processed.