Random Graphs (MAST90112)

  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. Time and interest permitting, we may cover some statistical applications.

Resources: We will cover a selection of material from the (free online) texts Topics and exercises

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]
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 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