Large deviations for sparse random graphs

Nicholas Cook


Please LOG IN to view the video.

Date: February 12, 2019


Let G = G(N, p) be an Erd˝os–R´enyi graph on N vertices (where each pair is connected by an edge independently with probability p). We view N as going to infinity, with p possibly going to zero with N. For a fixed graph H (such as the triangle on three vertices) what is the probability that G contains twice as many copies of H as we would expect? I will discuss recent progress on such “infamous upper tail” problems, which serve as a test bed for the emerging theory of nonlinear large deviations (Chatterjee–Dembo 2014). These problems also connect with issues in extending the theory of graph limits to handle sparse graphs. In particular, I will discuss our approach to the upper tail problems via new versions of the classic regularity and counting lemmas from extremal combinatorics, specially tailored to the study of random graphs in the large deviations regime.

This talk is based on joint work with Amir Dembo.


Created: Tuesday, February 12th, 2019