Induced Minors, Asymptotic Dimension, and Baker's Technique
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909729457963008 |
|---|---|
| author | Hickingbotham, Robert |
| author_facet | Hickingbotham, Robert |
| contents | Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). We prove that every hereditary class of bounded-degree graphs that excludes some graph as a fat minor has asymptotic dimension at most $2$, which is optimal. This makes substantial progress on a question of Bonamy, Bousquet, Esperet, Groenland, Liu, Pirot, and Scott (J. Eur. Math. Soc. 2023).
The key to our proof is a notion inspired by Baker's technique (J. ACM 1994). We say that a graph class $\mathcal{G}$ has bounded Baker-treewidth if there exists a function $f \colon \mathbb{N} \to \mathbb{N}$ such that, for every graph $G\in \mathcal{G}$, there is a layering of $G$ such that the subgraph induced by the union of any $\ell$ consecutive layers has treewidth at most $f(\ell)$. We show that every class of bounded-degree graphs that excludes some graph as an induced minor has bounded Baker-treewidth. We discuss further applications of this result to clustered colouring and the design of linear-time approximate schemes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06190 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Induced Minors, Asymptotic Dimension, and Baker's Technique Hickingbotham, Robert Combinatorics Discrete Mathematics Group Theory Geometric Topology Metric Geometry Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). We prove that every hereditary class of bounded-degree graphs that excludes some graph as a fat minor has asymptotic dimension at most $2$, which is optimal. This makes substantial progress on a question of Bonamy, Bousquet, Esperet, Groenland, Liu, Pirot, and Scott (J. Eur. Math. Soc. 2023). The key to our proof is a notion inspired by Baker's technique (J. ACM 1994). We say that a graph class $\mathcal{G}$ has bounded Baker-treewidth if there exists a function $f \colon \mathbb{N} \to \mathbb{N}$ such that, for every graph $G\in \mathcal{G}$, there is a layering of $G$ such that the subgraph induced by the union of any $\ell$ consecutive layers has treewidth at most $f(\ell)$. We show that every class of bounded-degree graphs that excludes some graph as an induced minor has bounded Baker-treewidth. We discuss further applications of this result to clustered colouring and the design of linear-time approximate schemes. |
| title | Induced Minors, Asymptotic Dimension, and Baker's Technique |
| topic | Combinatorics Discrete Mathematics Group Theory Geometric Topology Metric Geometry |
| url | https://arxiv.org/abs/2508.06190 |