Description
The module introduces the probabilistic method, a powerful approach with many applications in combinatorics. The basic idea behind the method is that to prove that a combinatorial object with certain properties exists, it suffices to show that a random construction produces such an object with positive probability. The main topics covered in the module are the following: the basic method, linearity of expectation, alterations, the second moment, large deviations and the local lemma. Each of these topics will be presented along with applications in several different areas in combinatorics. The course will cover additional topics that will vary from year to year, including correlation inequalities, martingales, and various more intricate applications of aforementioned methods.
Module deliveries for 2024/25 academic year
Last updated
This module description was last updated on 19th August 2024.
Ìý