2019-07-29 Archontia Giannopoulou, The directed flat wall theorem

IBS Discrete Mathematics Group
IBS Summer Research Program on Algorithms and Complexity in Discrete Structures

Archontia Giannopoulou, The directed flat wall theorem
July 29 2019, Monday @ 10:00 AM ~ 11:00 AM
Room B232, IBS (기초과학연구원)

Speaker

Archontia Giannopoulou
National and Kapodistrian University of Athens, Greece
http://users.uoa.gr/~arcgian/

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 [Neil Robertson, Paul D. Seymour: Graph Minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B 89(1): 43-76 (2003)]. An important step towards this structure theorem is the Flat Wall Theorem [Neil Robertson, Paul D. Seymour: Graph Minors .XIII. The Disjoint Paths Problem. J. Comb. Theory, Ser. B 63(1): 65-110 (1995)], which has a lot of algorithmic applications (for example, the minor-testing and the disjoint paths problem with fixed number terminals).
In this paper, we prove the directed analogue of this Flat Wall Theorem. Our result builds on the recent Directed Grid Theorem by two of the authors (Kawarabayashi and Kreutzer), and we hope that this is an important and significant step toward the directed structure theorem, as with the case for the undirected graph for the graph minor project.
Joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon.