Structure, randomness and universality
Date: Tuesday, October 31, 2017
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Location: G449 (Patil/Kiva)
Event Type: Seminar
Contact: Nardos Abbay, firstname.lastname@example.org
TALK: Structure, randomness and universality
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. 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.
Created by Nardos Abbay at Friday, October 20, 2017 at 10:25 AM.