Introduced in 1993 by Gromov in the context of geometric group theory, the asymptotic dimension of a graph class measures how much “contact” is necessary between balls of “bounded” diameter covering a graph in that class. This concept has connections with clustered coloring or weak diameter network decompositions. While it seems surprisingly fundamental, much remains unknown about this parameter and it displays intriguing behaviours. We will provide a gentle exposition to the area: from the state of the art to the main tools and questions, including some answers.
This is joint work with Nicolas Bousquet, Louis Esperet, Carla Groenland, François Pirot and Alex Scott.