Everyone is welcome to attend the next N&O seminar with Carla Groenland with the title 'Universal Graphs and Labelling Schemes'.
The talk will take place in L017 at CWI, along with zoom support for remote participants. For more information and registration to get the Zoom link via e-mail, please contact Willem Feijen (willem.feijen at cwi.nl), Samarth Tiwari (samarth.tiwari at cwi.nl) or Sven Polak (sven.polak at cwi.nl).
Abstract: How small can we make a graph, which contains all n-vertex graphs as an (induced) subgraph? This is related to the notion of adjacency labelling scheme and the recent refutation of the Implicit Graph Conjecture. We obtain asymptotically optimal results for hereditary graph classes (e.g. perfect graphs and triangle-free graphs) and also consider what happens if we change 'induced' to 'isometric'.
I will first discuss what universal graphs and labelling schemes are and why they are interesting. I will then give some intuition about what kind of techniques we used in our results (including Szemerédi regularity lemma and efficient dictionaries). Several interesting questions are left open.
This is based on joint work with Marthe Bonamy, Louis Esperet, Cyril Gavoille and Alex Scott.
