Course Meeting Times
Lectures: 2 sessions / week, 1.5 hours / session
Prerequisites
No specific classes are required, but the course presupposes mathematical maturity at the level of a first-year math graduate student, with basic knowledge of combinatorics, graph theory, and probability.
Course Description
This course is a graduate-level introduction to the probabilistic method, 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.
Topics
- Probabilistic method
- Linearity of expectation
- Alterations
- The second moment method
- The Chernoff bound
- The Lovász local lemma
- Correlation and Janson’s inequalities
- Martingale convergence and Azuma’s inequality
- Concentration of measure
- Entropy methods
- The occupancy method
Textbook
Alon, Noga and Joel H. Spencer. The Probabilistic Method. Wiley, 2016. ISBN: 9781119061953.
Grading
Grading is entirely based on problem sets. There are no exams.