Department of Computer Science

Benjamin Sudakov

Time: 4:00PM
Date: Tuesday, Sep. 9
Location:298 Carver
Host:Ryan Martin and Giora Slutzki (jointly hosted by Com S and Math)
Title:Turan theorem: generalizations and applications

Abstract: In typical extremal problem one wants to determine maximum cardinality of discrete structure with certain prescribed properties. Probably the earliest such result was obtain 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 for 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.

About the Speaker:

Dr. Benjamin Sudakovis a Professor of Mathematics at UCLA, incumbent of the David Saxon Presidential Term Chair. He received his Ph.D form Tel Aviv University in 1999. Before coming to UCLA he held positions in Princeton University and Institute for Advanced Study in Princeton. His research interests are Algebraic and Probabilistic Methods in Combinatorics, Extremal Graph and Hypergraph Theory, Ramsey Theory, Random Structures and Application of Combinatorics to Theoretical Computer Science. He is receipt of a Sloan Foundation Fellowship and NSF Career award.