Seminars & Colloquia Calendar
Structure, randomness and universality in graph theory
Noga Alon, (Princeton and Tel Aviv University)
Location: Hill 705
Date & time: Friday, 23 March 2018 at 4:00PM - 5:00PM
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 ones were initiated by Rado in the 60s, and received a considerable amount of attention over the years, partly motivated by algorithmic applications. The study of the subject combines probabilistic arguments and explicit, structured constructions. 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.