Random Graphs (MAST90112)
Lecturer: Nathan Ross
Office: 147 Peter Hall
Consultation times: After lectures (when available) and by appointment
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.
Time and interest permitting, we may cover some statistical applications.
Resources: We will cover a selection of material from the (free online) texts
Exercises: Roch: 2.1, 2.11, 2.12; vdHo: 5.8, 5.9* Degree distribution of Erdős Rényi random graph, coupling, total variation distance [Roch, Section 4.2; vdHo, Sections 2.2, 5.4]
Exercises: vdHo: 5.11*, 5.12* *The dependence of λ on n is not correct for these problems Component structure of Erdős Rényi random graph, branching processes, stochastic domination [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] Lectures Lectures 1 - 8 Summary (before classes moved online) Lecture 9: Concentration of Erdős Rényi degree distribution 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