- Series
- Graph Theory Seminar
- Time
- Tuesday, November 10, 2020 - 12:30pm for 1 hour (actually 50 minutes)
- Location
- https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
- Speaker
- Louis Esperet – Université Grenoble Alpes – louis.esperet@grenoble-inp.fr – https://oc.g-scop.grenoble-inp.fr/esperet/
- Organizer
- Anton Bernshteyn
Please Note: Note the unusual time!
The following are two classical questions in the area of universal graphs.
1. What is the minimum number of vertices in a graph that contains all $n$-vertex planar graphs as induced subgraphs?
2. What is the minimum number of edges in a graph that contains all $n$-vertex planar graphs as subgraphs?
We give nearly optimal constructions for each problem, i.e. with $n^{1+o(1)}$ vertices for Question 1 and $n^{1+o(1)}$ edges for Question 2. The proofs combine a recent structure theorem for planar graphs (of independent interest) with techniques from data structures.
Joint work with V. Dujmovic, C. Gavoille, G. Joret, P. Micek, and P. Morin.