Speaker: Louis Esperet
Title: Universal graphs for classes of dense graphs
Abstract:
A graph G is universal for some class F if it contains all the graphs of F as induced subgraph. The objective is to minimize the number of vertices of G. In this talk I will explain how to construct universal graphs for any given hereditary class of dense graphs, with a nearly optimal number of vertices. I will also explain several applications of our result: how to obtain nearly optimal universal posets (posets that contain all n-element posets), and how to encode reachability in digraphs in a nearly optimal way.
This is joint work with Marthe Bonamy, Carla Groenland, and Alex Scott