Asymptotic dimension of graph classes

Abstract: The notion of asymptotic dimension of graph classes is borrowed from an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In the talk, I will try to give some intuition for the definition and our proof techniques. Our main result is that each minor-closed family of graphs has asymptotic dimension at most $2$. I will also mention some corollaries to clustered colouring and CS notions such as weak sparse partition schemes and weak diameter network decompositions. A special case of our main result also implies that complete Riemannian surfaces have asymptotic dimension (even Assouad-Nagata dimension) at most $2$ (which was previously unknown).

This is based on joint work with M. Bonamy, N. Bousquet, L. Esperet, 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.