Monday, June 28, 3pm ET (8pm BST, 7am Tue NZST)
Carla Groenland, Utrecht University
Universal Graphs and Labelling Schemes
An induced universal graph for a graph class contains all graphs in the class as an induced subgraph. We construct induced universal graphs for all hereditary graph classes, and derive reachability labelling schemes for digraphs and comparability labelling schemes for posets from this. All these results are asymptotically optimal. This talk aims to give some intuition about these concepts and our techniques (which includes Szemerédi’s regularity lemma). We will also discuss a new venue of research: what if we strengthen induced to isometric? Several interesting questions are left open.
This is based on joint work with Marthe Bonamy, Louis Esperet, Cyril Gavoille and Alex Scott.