Required: Probability, Advanced Probability.
Recommended: Measure and integral.
Or permission of the instructor.
Course objectives
Understand the fundamentals of random graph theory.
Explore connections to combinatorics, probability and statistical physics.
Discuss typical properties of large real-world networks.
Survey principal stochastic models and methods for the analysis of networks.
Description
Networks are ubiquitous. The mathematical analysis of random models of networks was begun over half a century ago, most notably from the perspectives of probabilistic combinatorics and statistical physics. A most prominent model is the elegant Erdős-Rényi random graph (which has its origins as early as 1947) and this model has over the decades yielded many unexpected results and insights. In the past 15 years or so, there has been an explosive increase of research into probability spaces of graphs that exhibit real-world properties -- that is, large-scale properties exhibited by networks coming from, for example, biology, economics, high technology, and sociology. There are at least two major reasons for this explosion (aside from the huge pressure of interest from the aforementioned fields): one is that, practically speaking, algorithmics, statistics and computational power had advanced enough to be able to actually analyse and quantify this behaviour for massive networks such as the Internet; another is that, from many perspectives, the theory had sufficiently developed for the proposal and rigorous assessment of a wide range of candidate models of random graph. In this course, we shall follow this development, beginning with the Erdős-Rényi model, and eventually move towards more realistic models such as geometric, inhomogeneous, and preferential attachment random graph models.
Examination
The final grade is based on a combination of homework, a project/presentation, and/or (oral) examination.
Literature
Primary sources:
Alon and Spencer. The probabilistic method, 3rd ed.
Durrett. Random graph dynamics. (Available electronically through RU library.)
Janson, Łuczak and Ruciński. Random graphs.
Penrose. Random geometric graphs.
Selected research papers.
Schedule of lectures
Hoorcollege (Lectures) on Thursdays, 15:45-17:30, HG03.082; Werkcollege (Tutorials) on Wednesday, 9:30-11:15, HG03.085 in weeks 37-43, and on Wednesdays, 13:45-15:30, HG02.028 in weeks 46-51, 1-2.
Note: No lecture and no werkcollege in week 36. Opening lecture on Thursday, 10 September.
Week 36: No lecture and no werkcollege, but please fill out the survey.
10 September: Introductory lecture and overview of course.
11 September: Werkcollege.
16 September: Werkcollege.
17 September: Ramsey numbers.
23 September: Werkcollege.
24 September: Probabilistic method examples.
30 September: Werkcollege.
1 October: More examples of the probabilistic method.
7 October: Werkcollege.
8 October: Off-diagonal Ramsey numbers.
14 October: Werkcollege.
15 October: Introduction to random graphs.
21 October: Werkcollege.
22 October: Subgraph thresholds.
11 November: Werkcollege.
12 November: Concentration of G(n,p) parameters.
18 November: Werkcollege.
19 November: Asymptotics of the chromatic number.
25 November: Werkcollege.
26 November: Emergence of the giant.
2 December: Werkcollege.
3 December: Hitting times and connectivity.
9 December: Werkcollege.
10 December: Diameter and small-world phenomena.
15 December: Werkcollege.
16 December: Degrees and preferential attachment.
6 January: Werkcollege.
7 January: Prescribed degree distributions.
22 January: Final exam (room HG01.057, 12:30-15:30; room HG00.071, 12:30-16:30, for students who require extra facilities). See blackboard for course lecture notes, exam syllabus, practice exam.
Homework
Homework assignment 1 issued 24 September, due 30 September.
Homework assignment 2 issued 13 October, due 22 October.
Homework assignment 3 issued 22 November, due 3 December.
Homework assignment 4 updated 16 December, due 11 January.
Final exam on 22 January, 12:30 PM, location to be determined.
Project topics
Please email top 4 preferred topics by 20 November.
Combinatorial discrepancy.
Rodl nibble/semi-random method.
Lovasz local lemma.
Talagrand's inequality (or concentration inequalities in general).
Triangle-free process.
The infinite random graph.
Graph limits.
Zero-one laws in random graphs.
The diameter of the random graph.
Hamilton cycles or higher connectivity in the random graph.
Rumour spreading in random graphs.
Achlioptas processes and the power of two choices.
Random graphs with a given degree distribution.
Random geometric graphs.
Watts-Strogatz model.
Norros-Reittu model.
Or any other topic you propose related to the themes of the course.
kang
gmail