| |
Lecturer: Nathan Ross
Office: 147 Peter Hall
Consultation times: After lectures (when available) and by appointment
Class schedule:
Tues 11-12,
Thurs 1-2,
Fri 4:15-5:15
in Evan Williams Theatre
Assessment: Two assignments (30%) and end of semester exam (70%)
Subject overview: Random graphs (or networks) are
mathematical models now routinely used
in a wide range of areas and applications including statistics, computer science, and biology.
In this subject, we rigorously study structural properties of a number
of fundamental random graph models, such as Erdős Rényi and preferential attachment.
A complementary focus of the subject is on modern techniques in probability, such as
branching process approximations, couplings, and concentration inequalities, which are naturally highlighted in the analysis of these models.
Resources: We will cover a selection of material from the (free online) texts
Lectures and exercises
Lectures 1 - 8 Summary (before classes moved online)
Exercises: Roch: 2.1, 2.11, 2.12; vdHo: 5.8, 5.9
(The dependence of λ on n is not correct in vdHo 5.9.)
Lecture 9: Concentration of Erdős Rényi degree distribution
Exercises: vdHo: 5.11, 5.12
(The dependence of λ on n is not correct for these problems.)
Lecture 10: vdHo Exercises 5.8 and 5.9
Lecture 11: Erdős Rényi exploration process
Lecture 12: Branching processes
Lecture 13: Stochastic domination for Branching processes
Lecture 14: Branching process approximation of exploration process
Lecture 15: Random walk representation of branching processes
Lecture 16: Exponential tail bounds
Exercises: Binomial tail bounds
Lecture 17: Size of the largest component in Erdős Rényi random graphs
Lecture 18: Component sizes in subcritical Erdős Rényi random graphs
Lecture 19: Solutions to Assignment 1
Lecture 20: Giant component in supercritical Erdős Rényi random graphs
Lecture 21: Component sizes in supercritical Erdős Rényi random graphs
Lecture 22: Component sizes in supercritical Erdős Rényi random graphs
Lecture 23: Binomial tail bound exercises solutions
Lecture 24: Stein's method for Poisson approximation: preliminaries
Lecture 25: Stein's method for Poisson approximation
Lecture 26: Poisson approximation for subgraph counts
Lecture 27: Subgraph counts continued
Lecture 28: Implicit increasing couplings
Lecture 29: Preferential attachment tree
Lecture 30: Concentration of the degree distribution of the PA tree
Lecture 31: The average degree distribution of the PA tree
Lecture 32: The degree of a randomly chosen vertex of the PA tree
Lecture 33: Solutions to Assignment 2
Assessments
Assignment 1 (available 23 April, due 3 May)
Assignment 2 (available 26 May, due 5 June)
Exam (available on LMS 16 June, due 29 June)
Topics
Erdős Rényi random graph, thresholds, first and second moment methods
[Roch, Sections 2.2.1, 2.2.2, 2.2.4; vdHo, Section 5.3]
Degree distribution of Erdős Rényi random graph, coupling, total variation distance
[Roch, Section 4.2; vdHo, Sections 2.2, 5.4]
Component structure of Erdős Rényi random graph, branching processes, stochastic domination,
exponential tail bounds
[Roch, Sections 4.3.1, 5.1.1, 5.1.2, 5.2, 5.3.1, 5.3.3; vdHo, Sections 4.2, 4.3, 4.4]
Stein's method for Poisson approximation
[Ross, Sections 4.0, 4.1, 4.3]
Degree distribution of the preferential attachment tree, Azuma-Hoeffding inequality
[Roch, Sections 2.3.5, 3.2.1, 3.2.5; vdHo, Sections 2.5.2, 8.2, 8.4, 8.5, 8.6.1]
|