Contributors: Laboratoire Bordelais de Recherche en Informatique (LaBRI); Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS); Graphes, AlgOrithmes et AppLications (GOAL); Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS); Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL); Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL); Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon); Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL); Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS); Optimisation Combinatoire (G-SCOP_OC); Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP); Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ); Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ); Université Grenoble Alpes (UGA); Graphes, Algorithmes et Combinatoire - LISN (GALaC); Laboratoire Interdisciplinaire des Sciences du Numérique (LISN); Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Algorithmes, Apprentissage et Calcul (AAC); Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS); ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017); ANR-16-CE40-0009,GATO,Graphes, Algorithmes et TOpologie(2016); ANR-18-CE40-0032,GrR,Reconfiguration de Graphes(2018)
نبذة مختصرة : This paper is essentially a combination of arXiv:2007.03582 and the non-algorithmic part of arXiv:2007.08771, where some results in arXiv:2007.03582 are strengthened ; International audience ; The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science. We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minor-closed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad-Nagata dimension at most 2. Furthermore, our techniques allow us to prove optimal results for the asymptotic dimension of graphs of bounded layered treewidth and graphs of polynomial growth, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours.
Processing Request
No Comments.