标题： 诱导小图，渐近维数，贝克技术 显示英文标题

标题： Induced Minors, Asymptotic Dimension, and Baker's Technique

摘要： 渐近维数是度量空间的一个大尺度不变量，由Gromov（1993）引入。 我们证明了每个排除某些图作为胖子图的有界度图的遗传类的渐近维数最多为$2$，这是最优的。 这在Bonamy、Bousquet、Esperet、Groenland、Liu、Pirot和Scott（J. Eur. Math. Soc. 2023）提出的问题上取得了重大进展。 我们证明的关键是一个受Baker技巧（J. ACM 1994）启发的概念。 我们说一个图类$\mathcal{G}$具有有界Baker树宽，如果存在一个函数$f \colon \mathbb{N} \to \mathbb{N}$，使得对于每个图$G\in \mathcal{G}$，存在一个$G$的分层，使得任何$\ell$个连续层的并集所诱导的子图的树宽最多为$f(\ell)$。 我们证明了每个排除某些图作为诱导子图的有界度图类具有有界Baker树宽。 我们进一步讨论了该结果在聚类着色和线性时间近似方案设计中的应用。 显示英文摘要

摘要： 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.