Probabilistic Methods in Combinatorics (M.Stat 2026-27)
Probabilistic Methods in Combinatorics (M.Stat 2026-27)
Instructors Sourav Chakraborty and Arijit Ghosh
Status To begin from July 2026
Description Introduction to the probabilistic method and its applications
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings Tuesday and Friday from 4:10 PM - 6:00 PM
Syllabus
First moment methods
Alterations
Second moment methods
Local lemma
Concentration inequalities
Balls and bins
Correlation Inequalities
Martingales
Poisson Paradigm
Quasirandomness
Entropy
Containers
Dependent random choice
VC dimension and theory of sampling
Polynomial identity testing
Dimension reduction
References
[AS16] Noga Alon and Joel Spencer, The Probabilistic Method, 4th Edition, Wiley, 2016
[AZ18] Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK, Springer, 2018
[A26] James Aspnes, Notes on Randomized Algorithms, Lecture Notes, Yale University, 2026
[H11] Sariel Har-Peled, Geometric Approximation Algorithms, American Mathematical Society, 2011
[H18] Sariel Har-Peled, Class Notes for Randomized Algorithms, UIUC, 2018
[H26] Nick Harvey, A First Course in Randomized Algorithms, Lecture Notes, UBC, 2026
[H+26] Nick Harvey, A Second Course in Randomized Algorithms, Lecture Notes, UBC, 2026
[M+12] Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar, Foundations of Machine Learning, MIT Press, 2012
[MR95] Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995
[MU17] Michael Mitzenmacher and Eli Upfal, Probability and Computing, 2nd Edition, Cambridge University Press, 2017
[MV08] Jiří Matoušek and Jan Vondrák, The Probabilistic Method, Lecture Notes, Charles University, 2008
[N22] Nabil H. Mustafa, Sampling in Combinatorial and Geometric Set Systems, American Mathematical Society, 2022
[R19] Thomas Rothvoss, Probabilistic Combinatorics, Lecture Notes, UW, 2019
[S94] Joel Spencer, Ten Lectures on the Probabilistic Method, Second Edition, SIAM, 1994
[SB14] Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014
[V12] Roman Vershynin, Four lectures on Probabilistic Methods for Data Science, AMS, 2016
[Z22] Yufei Zhao, Probabilistic Methods in Combinatorics, Lecture Notes, MIT, 2022
Lecture details
Topics covered in Lecture 1
Introduction to the probabilistic method
Indicator random variable
Existence of a bipartite subgraph with at least half of the total edges
Reading materials:
Topics covered in Lecture 2
Introduction to Ramsey numbers
Lower bound on Ramsey numbers using random coloring
Erdos-Ko-Rado theorem, and its proof using random permutation
Reading materials:
Topics covered in Lecture 3
Existence of a Hamiltonian path in tournaments
Tournaments with many Hamiltonian paths
Sum-free subsets
Reading materials:
Topics covered in Lecture 4
Sperner's theorem, Bollobássystems, and LYMB inequality
Property-B: upper and lower bound using first moment methods
Reading materials:
Topics covered in Lecture 5
Introduction to list chromatic number
List chromatic number of complete bipartite graphs
Crossing lemma
Caro-Wei's theorem on independent sets in graphs
Proving Turan's theorem using the above result
Reading materials:
Topics covered in Lecture 6
Introduction to the alteration method using Ramsey number
Dominating set in graphs
Heilbronn's triangle problem
Derandomizing Caro-Wei's theorem on independent sets
Reading materials:
Topics covered in Lecture 7 (14 August 2026)
TBA
Reading materials:
TBA