Probability on graphs, winter term 2024/2025

Summary of lectures

• January 22: the interchange process [LP, Chapter 23.1], random transpositions, cycle structure of random permutations
• Further reading: for a good introduction to the cycle structure of the interchange process see this survey by Goldschmidt, Ueltschi and Windridge; I also recommend reading Schramm's classic paper
• January 15: Cheeger's inequality [LP, Theorem 13.10] - proof of the lower bound, basic comparison of Markov chains in L^2 [LP, Lemma 13.18], method of canonical paths [LP, Chapter 13.4], the diameter bound [LP, Theorem 13.26]
• Further reading: comparison using canonical paths is particularly nice for random walks on groups, see [LP, Chapter 13.4.2]
• January 8: bounds using all eigenvalues [LP, Lemma 12.18], application to the hypercube [LP, Example 12.19], the product condition for cutoff [S, Lemma 5], bottleneck ratio [LP, Theorem 7.4], Cheeger's inequality [LP, Theorem 13.10] - proof of the upper bound
• Further reading: a good example of how knowing all eigenvalues of the chain gives a very detailed understanding of the convergence to stationarity is the case of the cycle, see [S, Chapter 3.4]
• December 18: spectral techniques [LP, Chapter 12.1], relaxation time and its relation to the mixing time [LP, Chapter 12.2], examples: random walk on the cycle [LP, 12.3.1] and the hypercube [LP, Example 12.16]
• Further reading: for the relationship between the mixing time and the spectral gap for not necessarily reversible chains, see [S, Remark 8]; for a general theorem about eigenfunctions and eigenvalues of product chains see [LP, Chapter 12.4]
• December 11: random walk on the hypercube [LP, Example 5.3.2], distinguishing statistics [S, Chapter 2.1], strong stationary times [LP, Chapter 6.1, 6.3, 6.4, Examples 6.5.2 and 6.5.3]
• Further reading: for more examples of strong stationary times see [LP, Chapter 6.5]; for an interesting chapter about optimal strong stationary time see [LP, Chapter 6.7]
• December 4: basics of Markov chain mixing times, total variation distance and its properties [LP, Chapter 4.1 and S, Chapter 1.2], coupling characterization of TV distance [LP, Chapter 4.2], distance from stationarity and mixing time [LP, Chapter 4.5], the cutoff phenomenon [S, Chapter 1.4 - just the definition], bounding total variation distance by coupling [LP, Chapter 5.2], example: random walk on the cycle [LP, Example 5.3.2]
• Further reading: a neat alternative proof of submultiplicativity of distance to stationarity is given in [S, Chapter 1.3, Lemma 4]; please also take a look at [LP, Chapter 2] if you are unfamiliar if some families of Markov chains such as, e.g., birth and death chains
• November 27: graph limits, Benjamini-Schramm convergence, convergence of random regular graphs to the d-regulat tree, the grandfather graph, unimodularity (a mix of [C2, Chapter 1 and 2], [P, Chapter 14] and [vdH2, Chapter 2])
• Further reading: the theory of local graph limits is relatively new, so there is no definitive reference for the topic as of now; I encourage you to look up the aforementioned references
• November 20: random regular graphs, the configuration model [JŁR, Chapter 9.1], asymptotic distribution of cycles and its consequences [JŁR, Chapter 9.2]
• Further reading: the configuration model for a general degree sequence is treated in [FK, Chapter 11] or [vdH, Chapter 7]; a nice review of various models of regular graphs and their properties is given in this survey by Wormald; for an alternative proof of Poisson limit of cycle distribution using Stein-Chen method, I recommend these notes by Charles Bordenave (Theorem 2.17)
• November 13: variance estimate for the number of vertices in large components [vdH, Proposition 4.10], no components of intermediate size [vdH, Proposition 4.12], finishing up the proof of the existence of the giant component [vdH, Lemma 4.14], overview of the critical window [AS, Chapter 11.1]
• Further reading: for more details on the critical window, see [vdH, Chapter 5.1-5.2]; alternatively, take a look at the (relatively elementary) paper by Nachmias and Peres (link here) proving properties of the critical random graph with martingales other interesting things which we didn't cover in class include CLT for the giant component [vdH, Chapter 4.5] and discrete duality principle [vdH, Chapter 4.4.6]
• November 6: comparison of binomial and Poisson branching processes [vdH, Theorem 3.20], stochastic bounds on the largest component [vdH, Theorem 4.2, 4.3], size of the largest component in the subcritical regime [vdH, Theorem 4.4], proof strategy for the emergence of the giant component in the supercritical regime [vdH, Chapter 4.4], cluster tail and survival probability [vdH, Proposition 4.9]
• Further reading: for the full picture of the subcritical regime, take a look at [vdH, Chapter 4.3.3]; Strassen's theorem on stochastic domination (which was briefly mentioned in the lecture), is discussed in [vdH, Lemma 2.12]
• October 30: overview of the emergence of the giant component, introduction to branching processes [vdH, early part of Chapter 3.1], the random walk representation of branching processes [vdH, early part of Chapter 3.3], the hitting time theorem [vdH, Theorem 3.13 and 3.14]
• Further reading: the whole Chapter 3 of [vdH] is an extensive source of information about branching processes (I especially recommend reading about the duality principle and conditioning the process to die out or survive)
• October 23: connectivity threshold for G(n,p) [vdH, Theorem 5.8]
• Further reading: for a proof of Cayley's tree theorem, you can take a look at Chapter 26 of "Proofs from the Book" by Aigner and Ziegler - there are four different proofs given there; altogether the theorem has probably at least 10 different proofs in the literature
• October 16: first and second moment method, threshold for containing triangles (roughly [Z, Chapter 4]), Poisson limit at the threshold in the general case [JŁR, Theorem 3.19], a sketch of the large deviation princinple
• Further reading: we didn't discuss the other way of proving the Poisson limit (the Stein-Chen method), which is covered in [JŁR, Chapter 6.2]; a beautiful book covering the theory of large deviations for random graphs and many recent developments is Sourav Chatterjee's "Large Deviations for Random Graphs" (link)
• October 9: introduction to G(n,p) and G(n,M) models, threshold functions [JŁR, Chapter 1], every monotone property has a threshold [JŁR, Theorem 1.24], equivalence of the two models [JŁR, Proposition 1.12 and 1.13]
• Further reading: we discussed coarse and sharp thresholds very briefly, without stating the Friedgut-Kalai and Friedgut's theorem - you can find more in [JŁR, Chapter 1.6]; also, during the exercise session we discussed the Rado graph - a very nice survey by Peter Cameron can be found here

Problem sets

• Problem set 1
• Problem set 2
• Problem set 3
• Problem set 4
• Problem set 5
• Problem set 6
• Problem set 7
• Problem set 8
• Problem set 9
• Problem set 10
• Problem set 11

Literature

Random graphs

• S. Janson, T. Łuczak, A. Ruciński "Random Graphs" [JŁR]
• a classical textbook on random graph theory
• A. Frieze, M. Karoński "Introduction to Random Graphs" (book in progress, link here) [FK]
• a new textbook on random graphs, has quite a lot of overlap with [JŁR], but covers more combinatorial topics
• N. Alon, J. Spencer "The Probabilistic Method" [AS]
• the definitive textbook on the probabilistic method in combinatorics
• Y. Zhao "Probabilistic Methods in Combinatorics" (lecture notes, link here)[Z]
• very nice lecture notes covering some material close to the topic of this course for which we won't have time
• R. van der Hofstad "Random Graphs and Complex Networks, vol. 1" [vdH]
• a modern book on random graphs and networks, highly recommended
• R. van der Hofstad "Random Graphs and Complex Networks, vol. 2" [vdH2]
• second volume of the above
• N. Curien "A random walk among random graphs" (lecture notes, link here) [C]
• constantly updated lecture notes, covering many topics not considered elsewhere (such as random permutations or spectral measures)
• N. Curien "Random graphs: the local convergence point of view" (lecture notes, link here) [C2]
• lecture notes devoted to the theory of local graph limits
• G. Pete "Probability on Graphs and Groups", (book in progress, link here) [P]
• a wonderful book (maybe one the best math books I've seen) covering mostly probability on infinite graphs; also relevant to the Markov chains part of the course

Markov chains and mixing times

• D. Levin, Y. Peres "Markov Chains and Mixing Times" [LP]
• the definitive textbook on mixing times in Markov chains
• J. Salez "Mixing times of Markov chains" (lecture notes, link here)[S]
• very nice and concise lecture notes, with a slightly different approach than in some other sources
• N. Berestycki "Mixing Times of Markov Chains: Techniques and Examples" (lecture notes, link here)[B]
• another set of very well-written lecture notes
• L. Saloff-Coste "Random Walks on Finite Groups" [S-C]
• good lecture notes on an important class of random walks