论文标题
次要家庭及以后的渐近维度
Asymptotic dimension of minor-closed families and beyond
论文作者
论文摘要
度量空间的渐近维度是Gromov引入的几何群体理论中的一个重要概念。本文考虑的度量空间是其基础空间是图形的顶点集，其指标是图中的距离函数。标准的紧凑性参数表明，考虑有限图类别的渐近维度足够。 在本文中，我们证明了任何适当的次要封闭式家庭的渐近维度，有界树宽的任何类别以及任何有界分层的树宽的图形最多的2、1和2分别是。第一个结果解决了富士和帕帕索格鲁的问题；第二和第三结果解决了Bonamy，Bousquet，Esperet，Groenland，Pirot和Scott的许多问题。这些渐近维度的界限是最佳的，并改善了文献中的许多结果。我们的证明可以转化为线性或二次时间算法，以查找目睹渐近维度的覆盖物，这等同于为图寻找弱直径着色。我们证明的关键要素是一种统一的机制，讲述了图形类别的渐近维度，这些渐近分类在遗传类别上具有有限的粘附，并具有已知的渐近造成维度，这可能具有独立的兴趣。
The asymptotic dimension of metric spaces is an important notion in geometric group theory introduced by Gromov. The metric spaces considered in this paper are the ones whose underlying spaces are the vertex-sets of graphs and whose metrics are the distance functions in graphs. A standard compactness argument shows that it suffices to consider the asymptotic dimension of classes of finite graphs. In this paper we prove that the asymptotic dimension of any proper minor-closed family, any class of graphs of bounded tree-width, and any class of graphs of bounded layered tree-width are at most 2, 1, and 2, respectively. The first result solves a question of Fujiwara and Papasoglu; the second and third results solve a number of questions of Bonamy, Bousquet, Esperet, Groenland, Pirot and Scott. These bounds for asymptotic dimension are optimal and improve a number of results in the literature. Our proofs can be transformed into linear or quadratic time algorithms for finding coverings witnessing the asymptotic dimension which is equivalent to finding weak diameter colorings for graphs. The key ingredient of our proof is a unified machinery about the asymptotic dimension of classes of graphs that have tree-decompositions of bounded adhesion over hereditary classes with known asymptotic dimension, which might be of independent interest.
