Selected results in temporal graph theory (Arnaud Casteigts, UNIGE)

05.12.2023 10:30

A temporal graph is a graph whose edges are only present at certain points in time. These graphs received a growing attention over the past two decades, due to their ability to model various types of dynamic networks. On the theoretical side, temporal graphs are quite different from static graphs. For instance, reachability (defined in terms of paths that traverses edges in chronological order) is not transitive. This and other features have important consequences, both structural and algorithmic, most questions being computationally hard.
In this talk, I will review some basic results in this young field, with a focus on sparse spanning substructures. Such structures do not always exist (yet, they are guaranteed in a probabilistic sense). If time permits, I will also mention aspects related to the enumeration of temporal graphs and some properties of their groups of automorphisms.

Lieu

Bâtiment: Conseil Général 7-9

Room 1-05, Tuesday 05.12.2023, Séminaire "Groupes et Géométrie"

entrée libre