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
Chernoff-Hoeffding Inequality
Entropy
Lovász local lemma
Dependent random choice
VC dimension and theory of sampling
Balls and bins, and the power of two choices
Correlation inequalities
Janson inequalities
Concentration of measure
Dimension reduction
Poisson paradigm
Quasirandomness
Containers
Polynomial identity testing
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]
Topics covered in Lecture 11
Tutorial session
Topics covered in Lecture 12
Independence from a set of events and dependency digraphs
Random variable model
Hypergraph coloring and Boolean satisfiability problem (SAT)
Statement of 2-coloring integers and arithmetic progressions (Beck's theorem)
Lovász local lemma (symmetric and general forms)
Proof of the Lovász local lemma (general form)
Reading materials:
Topics covered in Lecture 13
Applications of the Lovász local lemma
2-coloring k-uniform hypergraphs
2-coloring non-uniform hypergraphs
Compactness argument for coloring non-uniform hypergraphs on an infinite vertex set
Erdős and Lovász result on k-coloring the real line
Beck's theorem 2-coloring integers and arithmetic progressions
Reading materials: