Computer Science/Discrete Mathematics Seminar II

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.