401-3054-14L  Probabilistic Methods in Combinatorics

SemesterAutumn Semester 2018
LecturersB. Sudakov
Periodicitynon-recurring course
Language of instructionEnglish


AbstractThis 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.
Objective
ContentThe 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.