Asymptotic dimension of graphs

Abstract: The asymptotic dimension of a metric space is a notion introduced by Gromov in the 90s, in connection with geometric group theory. In the special case of the shortest path metric associated to a graph, a related notion, called "weak network decomposition" 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.

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.

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.