Asymptotic dimension of graphs

09.03.2021 15:00 - 17:00

Louis Esperet (Grenoble)

Introductory talk

The asymptotic dimension of a metric space is a notion introduced by Gromov in the 90s. I will explain the different definitions (with an emphasis on discrete spaces), and its connection with group theory. I will give several basic examples and proofs, and remark that in the special case of the shortest paths metric associated to a graph, a related notion has been independently considered by theoretical computer scientists, with a different motivation. I will also explain some links with the classical notion of graph coloring, and some variants that have been studied since the end of the 90s.

Research Talk

A class of graphs is minor-closed if any graph obtained from a graph in the class by deleting vertices or edges, or contracting edges, is still in the class. A typical example is the class of all graphs embeddable on a fixed surface. 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 to a problem raised by Ostrovskii and Rosenthal on minor excluded groups.

Joint work with M. Bonamy, N. Bousquet, C. Groenland, C.-H. Liu, F. Pirot, and A. Scott.



G. Arzhantseva, A. Evetts
Join online at link below, using Chrome.