Constant Congestion Brambles in Directed Graphs

Abstract

The Directed Grid Theorem, stating that there is a function f such that a directed graph of directed treewidth at least f(k) contains a directed grid of size at least k as a butterfly minor, after being a conjecture for nearly 20 years, was proved in 2015 by Kawarabayashi and Kreutzer. However, the function f obtained in the proof is very fast growing. In this work, we show that if one relaxes directed grid to bramble of constant congestion, one can obtain a polynomial bound. More precisely, we show that for every k ≥ 1 there exists t = O(k48 log13 k) such that every directed graph of directed treewidth at least t contains a bramble of congestion at most 8 and size at least k.