MIT Combinatorics Seminar

Dependent Random Choice and Ramsey-Turan Type Problems

Benny Sudakov (Princeton University)

Friday, April 1, 2005   4:15 pm    Room 2-338


The Probabilistic Method is a powerful tool in tackling many problems in Combinatorics and it belongs to those areas of mathematical research that have experienced a most impressive growth in recent years. One of the parts of discrete mathematics where this approach has proved to be especially useful is Extremal Combinatorics. In fact, many of the strongest results in this area in the last few decades are examples of this method.

In this talk we discuss a few recent applications of this methodology. In particular, we present simple but yet surprisingly powerful probabilistic arguments which were used recently to make progress on some long-standing Ramsey and Turan type problems.