This semester (Winter 2018/19), I will be teaching the graduate course:
Seminar in Probability and Stochastic Processes (098435)
(Hebrew: סמינר בהסתברות ותהליכים סטוכסטיים)
This is an assigned title. This year’s course will be 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.
Logistics: Lectures are 9.30 – 11.20 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.
There will definitely be a lecture on Sunday 2nd December.
Prerequisites: A standard undergraduate course in probability will be very useful, 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. The details will be established by consultation once it is clear how many are in this position.
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 cover all these topics and very much more, sometimes with alternative methodology.