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. Time and interest permitting, we may cover some statistical applications. Resources: We will cover a selection of material from the (free online) texts
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 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 