Thursday, 7th June 2007, 4:00 pm

Mathematics Building, Lecture Hall 2

Benny Sudakov

(Princeton)

"Turan's Theorem: Generalizations and Applications"

** Abstract: **
In a typical extremal problem one wants to determine maximum cardinality
of discrete structure with certain prescribed properties. Probably the
earliest such result was obtained 100 years ago by Mantel who computed the
maximum number of edges in a triangle-free graph on n vertices. This was
generalized by Turan to all complete graphs and became a starting point
of Extremal Graph Theory.

In this talk we survey several classical problems and results in this area and present some interesting applications of Extremal Graph Theory to other areas of mathematics. We also describe a recent surprising generalization of Turan's theorem which was motivated by question in Computational Complexity.

Light refreshments will be served in the faculty lounge at 3:30.

List of talks, 2006-07

Archive of talks