Probability on graphs, summer term 2019/2020
Summary of lectures
- February 25: introduction, G(n,p) and G(n,m) models, threshold functions, threshold for containing triangles, Harris' inequality
- March 3: threshold for containing general subgraphs, Janson's inequalities, large deviations for subgraph counts
- March 10: limiting Poisson distribution of subgraph counts at the threshold, threshold for connectivity
- March 17: threshold for connectivity (continued), sharp thresholds (Friedgut-Kalai's and Friedgut's theorem)
- March 24: the emergence of the giant component, properties of branching processes
- March 31: absence of the giant component in the subcritical case and its emergence in the supercritical case
- April 7: the emergence of the giant component in the supercritical case (continued), the critical regime
- April 21: introduction to mixing times, total variation distance
- April 28: bounding mixing times by coupling and by strong stationary times
- May 5: spectral methods, eigenvalues and eigenfunctions, relaxation time
- May 12: lower bounds via bottleneck ratio, Cheeger's inequality
- May 19: lower bounds via distinguishing statistics, the cutoff phenomenon
- May 26: comparison methods, canonical paths, random walks on groups
- June 2: the interchange process, applications of comparison methods
- June 9: macroscopic cycles in the interchange process
Problem sets
Literature