Cycles of Well-Linked Sets II: an Elementary Bound for the Directed Grid Theorem
In 2015, Kawarabayashi and Kreutzer proved the Directed Grid Theorem - the generalisation of the well-known Excluded Grid Theorem to directed graphs - confirming a conjecture by Reed, Johnson, Robertson, Seymour and Thomas from the mid-nineties. The theorem states that there is a function $f$ such that every digraph of directed treewidth $f(k)$ contains a cylindrical grid of order $k$ as a butterfly minor. However, the given function grows faster than any non-elementary function of the size of the grid minor. More precisely, it is larger than a power tower whose height depends on the size of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.11716
curl -X POST /api/v1/records/arxiv/2602.11716/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.11716/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'