Random Graphs (B.Stat, 2023-24)
Instructors Sourav Chakraborty and Arijit Ghosh
Status Completed
Teaching assistant Swarnalipa Datta
Description Introduction to random graphs
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings Wednesdays and Fridays from 11:00 am to 1:00 pm
Syllabus
Tools from Probability
First and Second moment methods
Coupling of random variables
Concentration inequalities for sum of independent random variables
Introduction to branching processes
Correlation inequalities
Janson inequalities
Galton-Watson Process
Introduction to Martingales
Topics from Random Graphs
Erdős-Rényi random graphs and uniform random graphs
Equivalence between two models of random graphs
Introduction to thresholds and phase transition
Evolution of random graphs
References
[AZ18] Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK, 6th Edition, 2018
[AS16] Noga Alon and Joel Spencer, The Probabilistic Method, 4th Edition, Wiley, 2016
[B01] Béla Bollobás, Random Graphs, 2nd Edition, Cambridge University Press, 2021
[BHK20] Avrim Blum, John Hopcroft, and Ravindran Kannan, Foundations of Data Science, Cambridge University Press, 2020
[FK15] Alan Frieze and Michał Karoński, Introduction to Random Graphs, Cambridge University Press, 2015
[H18] Sariel Har-Peled, Randomized Algorithms, Lecture Notes, UIUC, 2018
[H17] Remco van der Hofstad, Random Graphs and Complex Networks, Cambridge University Press, 2017
[M94] Ketan Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, Prentice Hall, 1994
[MU05] Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005
[MU17] Michael Mitzenmacher and Eli Upfal, Probability and Computing, 2nd Edition, Cambridge University Press, 2017
[M16] Robert Morris, The Method of Hypergraph Containers, Lecture Notes, 2016
[MR95] Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995
[R19] Thomas Rothvoss, Probabilistic Combinatorics, Lecture Notes, UW Seattle, 2019
[Z22] Yufei Zhao, Probabilistic Methods in Combinatorics (Lecture Notes), Fall 2022, MIT, 2022
Lecture details
Topics covered in Lecture 1
Introduction to the course
Models of random graphs:
Erdős–Rényi model
Uniform random graph model
Introduction to "The Probabilistic Method"
Size of Max-Cut in a fixed graph
Erdős' lower bound on diagonal Ramsey number
Introduction to advanced topics:
Regularity Lemma
Expander Graphs
Reading materials:
Topics covered in Lecture 2
Indicator random variable and linearity of expectation
Alteration and improving the constant in the lower of diagonal Ramsey Number
Limitations of union bound and independence
Statement of symmetric Lovasz Local Lemma (LLL)
Showing existence of a satisfying assignment for sparse k-CNF using LLL
Improving diagonal Ramsey Number bound using LLL
Reading materials:
Topics covered in Lecture 3
Random permutations
Alternative proofs of some classical results in combinatorics using linearity of expectations and random permutations
YBLM inequality and Sperner's Theorem (Extremal Set Theory)
Bollobás set pairs inequality and (k,ℓ)-system
Erdős–Ko–Rado Theorem
Reading materials:
Topics covered in Lecture 4
Applications of alteration method:
Existence of large independent
Existence of small dominating set
Improved bound (over alteration method) for independent set using random permutations
Planar graphs and crossing number definition
Reading materials:
Additional reading materials:
Cosmin Pohoata's blog on independent sets in graphs and hypergraphs
Triangle-free graphs and Shearer's bound for independent set
Alon's generalization of Shearer's result
Topics covered in Lecture 5
Proof of crossing lemma by using
random induced subgraphs,
Euler formula for planar graphs, and
first moment method
Existence of a small dominating set using alteration
Existence of graphs with large girth and also large chromatic number using
Erdős–Rényi random graph model, and
the method of alteration
Reading materials:
Topics covered in Lectures 6 and 7
Variance, Covariance, and their properties
Chebyshev's inequality and its simple consequences
Introduction to thresholds in random graphs in Erdős–Rényi and uniform random graph models
Threshold for the existence of a triangle and, more generally, a fixed graph as a subgraph in Erdős–Rényi random graph
Coupling of random variables
Existence of threshold for monotone properties
Sharp and coarse threshold
Examples of monotone properties in graphs
Reading materials:
Sections 4.1, 4.2, and 4.3 in Chapter 4 from [Z22]
Topics covered in Lecture 8
Clique number of Erdős–Rényi random graphs and its two point concentration
Introduction to subdivisions and minors of a graph
Difference between subdivisions and minors
Statements of Hadwiger's Conjecture and Hajós' Conjecture
Chernoff bound for Binomial random variables
Disproving Hajós' Conjecture using the above concentration bounds and Erdős–Rényi random graphs
Reading materials:
Topics covered in Lecture 9
Chernoff Bounds for sum of independent random variables
Better concentration bounds for some special cases
Hoeffding's Bound for sum of bounded independent random variables
Introduction to Discrepancy of set systems
Coupling in uniform random graph model using random permutation
Reading materials:
Topics covered in Lecture 10
Connections between Erdős–Rényi and uniform graph models
Connecting Erdős–Rényi and uniform graph models using second moment method
Reading materials:
Chapter 1 from [FK15]
Topics covered in Lecture 11
Connecting Erdős–Rényi and uniform graph models using second moment method (continuation)
Introduction to Correlation inequalities
Reading materials:
Topics covered in Lecture 12
Harris-FKG inequality and its proof
Application of Harris-FKG inequality
Reading materials:
Topics covered in Lecture 13
Topics covered in Lecture 14
Revisit Lovász Local Lemma
Lopsided Lovász Local Lemma and its proof
Reading materials:
Topics covered in Lecture 15
Applications of Lovász Local Lemma
Applications of Harris inequality and Janson's inequality
Reading materials:
Topics covered in Lecture 16
Recall Breadth First Search (BFS)
Recall Chernoff bounds for Binomial distribution
Evolution of random graphs:
Analysis of the sub-critical regime of random graphs using BFS
Reading materials:
Chapter 2 from [FK15]
Topics covered in Lecture 17
Structure of the connected components in the sub-critical regime
Introduction to Galton-Watson Process
Emergence of the giant component in the super-critical regime of random graphs
Reading materials:
Chapter 2 from [FK15]
Topics covered in Lecture 18
Introduction to Galton-Watson Process and extinction probability
Probability generating function
Extinction probability and fixed point of probability generating function
Examples of Galton-Watson process
Binomial distribution
Poisson distribution
Topics covered in Lecture 19
Min-cut in graphs
Karger's randomized algorithm for computing min-cut
Speed-up of Karger's algorithm using Galton-Watson process
Reading materials:
See Chapter 3 from [H18]
Topics covered in Lecture 20
Analysis of the connected components in the super-critical regime using Galton-Watson process
Reading materials:
See Chapter 2 from [FK15]