Probabilistic Methods in Combinatorics
Introduction to the probabilistic method, a fundamental and powerful technique in combinatorics and theoretical computer science. Focuses on methodology as well as combinatorial applications. Suitable for students with strong interest and background in mathematical problem solving. Topics include linearity of expectations, alteration, second moment, Lovasz local lemma, correlation inequalities, Janson inequalities, concentration inequalities, entropy method.
Fall 2022
This course is a graduate-level introduction to the probabilistic methods, a fundamental and powerful technique in combinatorics and theoretical computer science. The essence of the approach is to show that some combinatorial object exists and prove that a certain random construction works with positive probability. The course focuses on methodology as well as combinatorial applications.
Readings
- Alon, Noga and Joel H. Spencer. The Probabilistic Method . Wiley, 2016. ISBN: 9781119061953. (The fourth edition is the latest, but earlier editions suffice.)
Prerequisites & course information
Prereq: ( 18.211 , 18.600 , and ( 18.100A , 18.100B , 18.100P , or 18.100Q )) or permission of instructor Acad Year 2027-2028: G (Fall) Acad Year 2028-2029: Not offered 3-0-9 units
Sources
- Course catalogue ↗2026–2027
- MIT OpenCourseWare ↗Fall 2022
- MIT OCW calendar ↗
- MIT OCW syllabus ↗
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.