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
Existence of graphs with high girth and high chromatic number
Random greedy coloring and Property-B
Reading materials:
Topics covered in Lecture 8
Chebyshev's inequality
Chernoff-Hoeffding Inequality
A probabilistic proof of the Weierstrass Approximation Theorem
Distinct sum problem
Reading materials:
Topics covered in Lecture 9
Introduction to hashing
Fredman, Komlós, and Szemerédi (FKS) hashing
Reading materials:
Chapter 15 from [MU17]
Topics covered in Lecture 10
Introduction to entropy
Shannon's Noisy-Channel Coding Theorem
Reading materials:
Chapter 10 from [MU17]