Scaling limits of random graphs - Lecture 1
Date: Tue, Jun 6, 2017
Location: PIMS, University of British Columbia
Conference: PIMS-CRM Summer School in Probability 2017
Subject: Mathematics
Class: Scientific
Abstract:
In the last 30 years, random combinatorial structures and their limits have been a flourishing area of research at the interface between probability and combinatorics. In this minicourse, I hope to show you some of the beautiful theory that arises when considering scaling limits of random trees and graphs.
Trees are fundamental objects in combinatorics and the enumeration of different classes of trees is a classical subject. In the first part of the minicourse, we will take as our basic object the genealogical tree of a critical Galton-Watson branching process. (As well as having nice probabilistic properties, this class turns out to include various natural types of random combinatorial tree in disguise.) In the same way as Brownian motion is the universal scaling limit for centred random walks of finite step-size variance, it turns out that all critical Galton-Watson trees with finite offspring variance have a universal scaling limit, Aldous' Brownian continuum random tree. In the infinite variance case, assuming certain tail conditions for the offspring distribution, other scaling limits arise, the so-called stable trees.
The simplest model of a random network is the Erdős-Rényi random graph: we take n vertices, and include each possible edge independently with probability p. One of the most well-known features of this model is that it undergoes a phase transition. Take p=c/n. Then for c<, the components have size O(log n), whereas for c>1, there is a giant component, comprising a positive fraction of the vertices, and a collection of O(log n) components. In the second part of this minicourse, we will focus on the critical setting, c=1, where the largest components have size on the order n2/3, and are "close" to being trees, in the sense that they have only finitely many more edges. We will see how to use a comparison with a branching process in order to derive the scaling limit of the critical Erdős-Rényi random graph.
Time permitting, we will then move on to consider the more general setting of a critical random graph generated according to the configuration model with independent and identically distributed degrees. Here, it is possible to obtain the same scaling limit as in the Erdős-Rényi case, but also others related to the stable trees.
