Noga Alon @ Theory Lunch

Title: Sparse universal graphs

Abstract:
What is the minimum possible number of vertices of a graph that contains every k-vertex graph as an induced subgraph ? What is the minimum possible number of edges in a graph that contains every k-vertex graph with maximum degree 3 as a subgraph ? These questions and related one were initiated by Rado in the 60s, and received a considerable amount of attention over the years, partly motivated by algorithmic applications and the tight connection to adjacency labeling schemes. I will survey the topic focusing on a recent asymptotic solution of the first question, where an asymptotic formula, improving earlier estimates by several researchers, is obtained by combining combinatorial and probabilistic arguments with group theoretic tools.