Nick Cook




Monday, January 14, 2019 - 3:00pm to 4:00pm


RH 306

Let $G=G(N,p)$ be an Erdos--Renyi 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 tail estimates for counts of any fixed subgraph. These problems serve as a test bed for the emerging theory of nonlinear large deviations, and 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.