401-3054-14L Probabilistic Methods in Combinatorics
|Semester||Autumn Semester 2020|
|Periodicity||two-yearly recurring course|
|Language of instruction||English|
|Abstract||This course provides a gentle introduction to the Probabilistic Method, with an emphasis on methodology. We will try to illustrate the main ideas by showing the application of probabilistic reasoning to various combinatorial problems.|
|Content||The topics covered in the class will include (but are not limited to): linearity of expectation, the second moment method, the local lemma, correlation inequalities, martingales, large deviation inequalities, Janson and Talagrand inequalities and pseudo-randomness.|
|Literature||- The Probabilistic Method, by N. Alon and J. H. Spencer, 3rd Edition, Wiley, 2008.|
- Random Graphs, by B. Bollobás, 2nd Edition, Cambridge University Press, 2001.
- Random Graphs, by S. Janson, T. Luczak and A. Rucinski, Wiley, 2000.
- Graph Coloring and the Probabilistic Method, by M. Molloy and B. Reed, Springer, 2002.