Structure, randomness and universality

Speaker: Noga Alon

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

Public: Yes

Location: G449 (Patil/Kiva)

Event Type: Seminar

Room Description:

Host:

Contact: Nardos Abbay, nardos@csail.mit.edu

Relevant URL:

Speaker URL:

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) 2017.

Created by Nardos Abbay Email at Friday, October 20, 2017 at 10:25 AM.