CSE 599 - The Probabilistic Method in Combinatorics

Tue,Thu 10:30-11:50 at CSE 503.

The course will cover the basic ingredients of the Probabilistic Method (such as the 1st and 2nd moment methods) and then proceed to more advanced techniques such as correlation inequalities, VC dimension and expander graphs. The course will closely follow the Alon-Spencer book and in the same spirit it will aim in each topic to introduce a method or tool and then demonstrate its applications in Combinatorics and Computer Science.

• Week 1 : The basic method (Mar 30, Apr 1)
• Week 2 : Linearity of expectation (Apr 6, Apr 8)
• Week 3 : The second moment method (Apr 13, Apr 15)
• Week 4 : Alterations (Apr 20, Apr 22)
• Week 5 : Lovasz's Local Lemma (Apr 27, Apr 29)
• Week 6 : Correlation inequalities (May 4, May 6))
• Week 7 : Martingales (May 20))
• Week 8 : Large deviation inequalities
• Week 9 : Vapnik-Chervonenkis Dimension
• Week 10 : Expanders