Probability on graphs, winter term 2024/2025

Summary of lectures

• 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

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