Asymptotic dimension of minor-closed families and beyond

• Main Author: Liu, Chun-Hung
• Format: Article in Journal/Newspaper
• Language: unknown
• Published: arXiv 2020
• Subjects: Combinatorics math.CO; Discrete Mathematics cs.DM; FOS Mathematics; FOS Computer and information sciences; Groenland
• Online Access: https://dx.doi.org/10.48550/arxiv.2007.08771; https://arxiv.org/abs/2007.08771

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.