Probability on graphs and lattices (Oxford MT2019 SC9)
In case of disaster with the Canvas software:
In Winter 2018/19, I taught the graduate course:
Seminar in Probability and Stochastic Processes (098435)
(Hebrew: סמינר בהסתברות ותהליכים סטוכסטיים)
This was an assigned title. The actual title is Random graphs and related topics. It is organised by the Faculty of Industrial Engineering, in which I am a postdoc. The content will be presented in a mathematical style, but the course is open to all students from all departments.
Summary, exercises and written assignment is here. Posts on this blog about individual lectures:
- Lecture 1: Introduction to random graphs
- Lecture 2: Connectivity threshold for G(n,p)
- Lecture 3: Coupling, comparing distributions
- Lecture 4: Exploration processes, and the hitting time theorem
- Lecture 6: Local limits
- Lecture 7: The giant component
- Lecture 8: Component sizes in the critical window
- Lecture 9: Inhomogeneous random graphs
- Lecture 10: The configuration model
Logistics: Lectures are 9.30 – 11.10 on Tuesday mornings, including a short break and time for questions. Venue is room 527 in the Bloomfield Building of Industrial Engineering. The first lecture is October 23rd, and the last lecture is January 22nd.
There will be no lecture in the week of January 1st, and the lectures due on October 30th, December 4th and December 25th will be perturbed to accommodate the local elections, Technion Hanukkah break and Christmas, respectively.
To make up for the local elections, there will definitely be a lecture on Sunday 2nd December.
Prerequisites: A standard undergraduate course in probability is essential, for example familiarity with Galton-Watson trees, and with modes of convergence of random variables.
Significant experience of graph theory is not necessary.
Credit: It will be possible for students of all levels to take the course for credit. Anyone wishing to do this should submit solutions to the starred exercises by February 28th, as well as a short (4-6 page) written assignment on one or more of the topics listed in the course summary document. PhD students may choose a topic with more flexibility if they wish.
The window for complaints about the grading policy is now closed.
The course will centre on the classical model of random graphs, G(n,p), following Erdos and Renyi, among others. We will explore various natural properties of these graphs heuristically, and then prove them rigorously, drawing on a wide range of tools applicable throughout discrete probability theory (in italics below). I aim to cover some of the following:
1. Erdos-Renyi random graph G(n,p): background, applications, thresholds for connectivity via second-moment methods
2. General threshold phenomena: couplings of G(n,p) and G(n,m), coupling as Markov processes, “with high probability” events etc, Harris and other correlation inequalities.
3. Subcritical G(n,p): classical tree enumeration methods following E+R, comparison with branching processes using stochastic domination.
4. Branching processes and local limits: revision of Galton-Watson trees, extinction and survival, Poisson BPs and the Borel distribution, Benjamini-Schramm convergence of random and deterministic graphs.
5. Supercritical G(n,p): Existence, uniqueness and concentration of the giant component, large deviations estimates, duality of supercritical and subcritical phases.
6. Coalescent processes (an aside): Reinterpreting component sizes in RG process, Flory and Smoluchowski coagulation equations, gelation, explicit solutions.
7. Exploration processes: Functional representations of GW trees and random graphs, hitting time theorem, scaling limits of trees.
8. The critical window of G(n,p): distributional scaling limit (following Aldous 97) for critical component sizes, via martingale method for convergence of Markov processes.
Beyond G(n,p): depending on time and audience interests, there are many options for final topics, for other related models such as the configuration model, and inhomogeneous random graphs, including similarities and differences in applicability and theory to G(n,p).
Resources and books
My aim is to keep the course self-contained. I will draw on van der Hofstad’s excellent recent notes and book fairly often.
The books of Bollobas, and of Janson, Luczak and Rucinski, and of Frieze and Karonski cover all these topics and very much more, sometimes with alternative methodology.