Large deviations of subgraph counts for sparse Erdős--Rényi graphs

Nicholas A. Cook, Amir Dembo

Published 2018-09-28Version 1

For each fixed integer $\ell\ge 3$ and $u>0$ we establish the leading order of the exponential rate function for the probability that the number of cycles of length $\ell$ in the Erd\H{o}s--R\'enyi graph $G(N,p)$ exceeds its expectation by a factor $1+u$, assuming $N^{-1/2}\ll p\ll 1$ (up to log corrections) when $\ell\ge 4$, and $N^{-1/3}\ll p\ll 1$ in the case of triangles. We additionally obtain the sharp upper tail for Schatten norms of the adjacency matrix, and for general subgraph counts in a narrower range of $p$, as well as the sharp lower tail for counts of seminorming graphs. As in recent works of Chatterjee--Dembo and Eldan on the emerging theory of \emph{nonlinear large deviations}, our general approach applies to "low complexity" functions on product spaces, though the notion of complexity used here is somewhat different. For the application to random graphs, our argument can be viewed as a quantitative refinement of the spectral approach to Szemer\'edi's regularity lemma for the setting of random graphs in the large deviations regime for counts of a given subgraph.