The price of homogeneity is polynomial
We provide explicit and polynomial bounds for the Homogeneous Wall Lemma which occurred for the first time implicitly in the $13$th entry of Robertson and Seymour's Graph Minors Series [JCTB 1990] and has since become a cornerstone in the algorithmic theory of graph minors. A wall where each brick is assigned a set of colours is said to be homogeneous if each brick is assigned the same set of colours. The Homogeneous Wall Lemma says that there exists a function $h$ that, given non-negative integers $q$ and $k$ and an $h(q,k)$-wall $W$ where each brick is assigned a, possibly empty, subset of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.01882
curl -X POST /api/v1/records/arxiv/2602.01882/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.01882/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'