Induced Minors, Asymptotic Dimension, and Baker's Technique
Robert Hickingbotham
渐近维数是Gromov(1993)引入的度量空间的大尺度不变量。我们证明了每个排除某个图作为胖次式的有界度图的遗传类，其渐近维数最多为2，这是最优的。这一结果在Bonamy、Bousquet、Esperet、Groenland、Liu、Pirot和Scott(J. Eur. Math. Soc. 2023)提出的问题上取得了实质性进展。我们证明的关键是受Baker技术(J. ACM 1994)启发的一个概念。我们说一个图类𝒢具有有界Baker树宽，如果存在一个函数f:ℕ→ℕ，使得对于𝒢中的每个图G，存在G的一个分层，使得由任意连续ℓ层的并集诱导的子图的树宽最多为f(ℓ)。我们证明了每个排除某个图作为诱导次式的有界度图类都具有有界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 �...
