Large deviations for sparse random graphs

Mathematics Colloquium Seminar

Nicholas Cook

Wednesday, January 23, 2019 -
12:00pm to 1:00pm
119 Physics

Let $G=G(N,p)$ be an Erd\H{o}s--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$. What is the probability that $G$ contains twice as many triangles (triples of vertices with all three pairs connected) as we would expect? I will discuss recent progress on this ``infamous upper tail" problem, and more generally on upper tail estimates for counts of any fixed subgraph. These problems serve as a test bed for the emerging theory of \emph{nonlinear large deviations}, and also connect with issues in extending the theory of \emph{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.

Last updated: 2019/06/16 - 10:18pm