401-3054-14L  Probabilistic Methods in Combinatorics

SemesterAutumn Semester 2020
LecturersB. Sudakov
Periodicitytwo-yearly recurring course
Language of instructionEnglish


401-3054-14 VProbabilistic Methods in Combinatorics2 hrs
Wed10:15-12:00HG E 5 »
B. Sudakov
401-3054-14 UProbabilistic Methods in Combinatorics1 hrs
Mon15:15-16:00HG G 3 »
B. Sudakov

Catalogue data

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.
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.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits6 credits
ExaminersB. Sudakov
Typesession examination
Language of examinationEnglish
RepetitionThe performance assessment is offered every session. Repetition possible without re-enrolling for the course unit.
Mode of examinationwritten 180 minutes
Additional information on mode of examinationBe aware that no exam repetition is offered until after the course itself will be taught again in a future semester.
Written aidsStudents are allowed to bring ONLY a printed copy of the lecture notes with no extra writing (highlighting and blank post-its are allowed).
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

Main linkWebsite of the course (Moodle)
Only public learning materials are listed.


401-3054-14 UProbabilistic Methods in Combinatorics
Mon15:15-16:00HG G 3 »


There are no additional restrictions for the registration.

Offered in

Data Science MasterCore ElectivesWInformation
Doctoral Department of MathematicsGraduate SchoolWInformation
Electrical Engineering and Information Technology MasterRecommended SubjectsWInformation
Electrical Engineering and Information Technology MasterSpecialisation CoursesWInformation
Computer Science MasterFocus Elective Courses General StudiesWInformation
Computer Science MasterFocus Elective Courses Theoretical Computer ScienceWInformation
Computer Science MasterElective CoursesWInformation
Mathematics BachelorSelection: Mathematical Optimization, Discrete MathematicsWInformation
Mathematics MasterSelection: Mathematical Optimization, Discrete MathematicsWInformation