Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs $G(n,m)$ and $G(n,p)$

Abstract

We consider the question of determining the probability of triangle count deviations in the Erdős-Rényi random graphs $G(n,m)$ and $G(n,p)$ with densities larger than $n^{-1/2}(\log n{)}^{1/2}$. In particular, we determine the log probability $\log \mathbb{P}(N_{△}(G)>(1+\hat{I}´)p^3{n}^3)$ up to a constant factor across essentially the entire range of possible deviations, in both the $G(n,m)$ and $G(n,p)$ model. For the $G(n,p)$ model we also prove a stronger result, up to a $(1+o(1))$ factor, in the non-localised regime. We also obtain some results for the lower tail and for counts of cherries (paths of length $2$).