Summer Graduate School

by DeDelphin Sénizergues

The topic of random graphs is at the forefront of applied probability, and it is one of the central topics in multidisciplinary science where mathematical ideas are used to model and understand the real world. At the same time, random graphs pose challenging mathematical problems that have attracted the attention from probabilists and combinatorialists since the 1960, with the pioneering work of Erdös and Rényi. Around the turn of the millennium, very large data sets started to become available, and several applied disciplines started to realize that many real-world networks, even though they are from various different origins, share many fascinating features. In particular, many of such networks are small worlds, meaning that graph distances in them are typically quite small, and they are scalefree, in the sense that there are enormous differences in the number of connections that their elements make. In particular, such networks are quite different from the classical random graph models, such as proposed by Erdös and Rényi.

Spurred by these findings, many novel models have been introduced and properties have been investigated. In this school, our aim is three-fold.

First, we aim to describe the novel models invented since 2000 to describe real-world networks, as well as their topological properties. These models share that they are rather inhomogeneous. Basic models that extend beyond the Erdös-Rényi random graph, include generalized random graphs, the configuration model, and dynamic models such as the preferential attachment model. Topological properties of such models are by now relatively well understood, and we aim to discuss them. Key examples of such properties include their giant component sizes, critical connectivity behavior, graph distances and degree structure.

Second, we aim to study the asymptotic local behavior of random graphs (such as are encoded by their local weak limits). In some cases, explicit descriptions of the local weak limits are possible; this often involves constructions via branching processes. We further pass beyond their local descriptions, discussing representations in terms of random walks and related stochastic processes for the scaling limits of critical random graphs.

Finally, we aim to discuss network functionality, as described by stochastic processes on random graphs, such as random walks, interacting particle systems, or statistical mechanics models.

School Structure
There will be two lectures per day. There will be a problem session in the morning after Lecture 1, and one in the afternoon after Lecture 2. The problem sessions will generally be led by the Teaching Assistants, though the Lecturers will be involved to observe or lead discussion as well. The purpose of the sessions is to reinforce and deepen students’ understanding of the material from the lectures by working on problems and in certain cases, to discuss material relevant to future lectures. This will be done by discussion, question-and-answer, and problem-solving from problem sets. Activities may include presentation of solutions to problems assigned based on lectures, student or TA presentation of material relevant to lecture, or exercises and presentation of relevant background material. 

Suggested Prerequisites

• Chapters 1 and 2 of “Random Graphs and Complex Networks: Volume 1” by van der Hofstad. 
• Chapters 1-5 plus Chapters 7 Sections 7.1-7.5,7.7,7.8 of "Probability and Random Processes, Third Edition" by Geoffrey Grimmett and David Stirzaker 

For eligibility and how to apply, see the Summer Graduate Schools homepage