14:00
Consider all planar graphs on n vertices. What is the smallest graph that contains them all as induced subgraphs? We provide an explicit construction of such a graph on $n^{4/3+o(1)}$ vertices, which improves upon the previous best upper bound of $n^{2+o(1)}$, obtained in 2007 by Gavoille and Labourel.
In this talk, we will gently introduce the audience to the notion of so-called universal graphs (graphs containing all graphs of a given family as induced subgraphs), and devote some time to a key lemma in the proof. That lemma comes from a recent breakthrough by Dujmovic et al. regarding the structure of planar graphs, and has already many interesting consequences - we hope the audience will be able to derive more. This is based on joint work with Cyril Gavoille and Michal Pilipczuk.