Content
Random Graphs and Networks (FS 2019)
Lectures: Monday and Tuesday 10:15-12:00, Spiegelgasse 5, Room 05.001
Exercises: Thursday 8:15-10:00, Spiegelgasse 5, Room 05.001 (assistant T. Hayder)
Summary: This course gives an introduction to the theory of random graphs and to the percolation theory
Lectures content:
- Feb 18: Introduction; branching processes
- Feb 19: Branching processes and random walks, law of total progeny
- Feb 25: Poisson and Binomial branching process; ER graph - exploration algorithm
- Feb 26: Tail estimates for clusters of ER graph; subcritical phase.
- Mar 18: Supercritical phase of ER graph.
- Mar 19: Supercritical phase of ER graph; critical behaviour - introduction
- Mar 25: Typical size of largest critical ER clusters
- Mar 26: Distribution of their size
- Apr 1: Large critical GW trees, Aldous' CRT
- Apr 2: Shape critical ER clusters
- Apr 8: Generalised random graph
- Apr 9: GRG conditioned on degrees; Configuration model - definition
- Apr 15: Configuration model: simplicity
- Apr 16: Configuration model: local tree picture; Preferential attachment: degree of given vertex
- Apr 23: Preferential attachment model: degree sequence
- Apr 29: Percolation: intro, non-triviality of phase transition
- Apr 30: Percolation: basic tools
- May 6:Percolation: Ergodicity, Burton-Keane theorem
- May 7: Percolation: BK theorem (cont.), continuity properties of θ
- May 13: Subcritical regime: exponential decay
- May 14: Coarsegraining and supercritical regime
- May 21: Percolation in d=2
- May 27: cont.
- May 28: Smirnov's theorem
Questions for exercises:
- Sheet 1 for Feb 28
- Sheet 2 for March 7
- Sheet 3 for March 21
- Sheet 4 for March 28
- Sheet 5 for April 4
- Sheet 6 for April 11
- Sheet 7 for April 25
- Sheet 8 for May 2
- Sheet 9 for May 9
- Sheet 10 for May 16
- Sheet 11 for May 23
Literature:
- R. van der Hofstad: Random graphs and Complex Networks, CUP 2017. (primary source for random walk part)
- D. Aldous: Brownian excursions, critical random graphs, and the multiplicative coalescent, Annals of Probability 25, 1997. (research paper, used a part about the size distribution of critical ER cluster)
- G. Grimmett: Percolation, Springer 1999
- B. Bollobas, O. Riordan: Percolation, CUP 2006
Lecture notes: week 1, week 2, week 3, week 4, week 5, week 6, week 7. For the percolation part of the lecture, see my old notes, and for some parts (in particular the exponential decay in the sub-critical phase) the recent lecture notes by H. Dumunil-Copin.