Constant congestion brambles in directed graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910025823289344 |
|---|---|
| author | Masařík, Tomáš Pilipczuk, Marcin Rzążewski, Paweł Sorge, Manuel |
| author_facet | Masařík, Tomáš Pilipczuk, Marcin Rzążewski, Paweł Sorge, Manuel |
| contents | The Directed Grid Theorem, stating that there is a function $f$ such that a directed graphs 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, has been proven 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 \geq 1$ there exists $t = \mathcal{O}(k^{48} \log^{13} 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_08445 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Constant congestion brambles in directed graphs Masařík, Tomáš Pilipczuk, Marcin Rzążewski, Paweł Sorge, Manuel Combinatorics Discrete Mathematics 05C20 The Directed Grid Theorem, stating that there is a function $f$ such that a directed graphs 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, has been proven 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 \geq 1$ there exists $t = \mathcal{O}(k^{48} \log^{13} 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$. |
| title | Constant congestion brambles in directed graphs |
| topic | Combinatorics Discrete Mathematics 05C20 |
| url | https://arxiv.org/abs/2103.08445 |