Dependent Random Choice and Extremal Problems

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Dependent Random Choice and Extremal Problems
Speaker:Benny Sudakov
Affiliation:Princeton University and IAS
Date:Tuesday, December 13
Time/Room:10:30am - 12:30pm/S-101

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 give proof of celebrated Balog-Szemeredi-Gowers lemma. We also show how this arguments can be used to make progress on some long-standing Ramsey-type problems.