Quicklists
Javascript must be enabled

Nicholas Cook : Large deviations for sparse random graphs

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.

Add to Favorites

Please select playlist name from following

Create new playlist

Report Video

Please select the category that most closely reflects your concern about the video, so that we can review it and determine whether it violates our Community Guidelines or isn’t appropriate for all viewers. Abusing this feature is also a violation of the Community Guidelines, so don’t do it.

0 Comments

Comments Disabled For This Video