Probability on graphs, winter term 2024/2025

Summary of lectures

• 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

Literature

• 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" [vdH]
• a modern book on random graphs and networks, highly recommended
• 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 graph limits or spectral measures)
• D. Levin, Y. Peres "Markov Chains and Mixing Times" [LP]
• the definitive textbook on mixing times in Markov chains
• 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
• L. Saloff-Coste "Random Walks on Finite Groups" [S-C]
• good lecture notes on an important class of random walks