Home

Research

Teaching

Contact



 

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.

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]