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 1112, Thurs 12, Fri 4:155: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 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, AzumaHoeffding 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] 