Marcelo Garlet Milani, Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem

In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem. The theorem states the existence of a function f such that every digraph of directed tree-width f(k) contains a cylindrical grid of order k as a butterfly minor, but the given function grows non-elementarily with the size of the grid minor.

We present an alternative proof of the directed grid theorem, first proven by Kawarabayashi and Kreutzer in 2015, which is conceptually much simpler, more modular in its composition and also improves the upper bound for the function f to a power tower of height 22.

Our proof is inspired by the breakthrough result of Chekuri and Chuzhoy, who proved a polynomial bound for the excluded grid theorem for undirected graphs. We translate a key concept of their proof to directed graphs by introducing cycles of well-linked sets (CWS), and show that any digraph of high directed tree-width contains a large CWS, which in turn contains a large cylindrical grid.

This is joint work with Meike Hatzel, Stephan Kreutzer and Irene Muzi.