Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph $G(n,m)$: The Lower Tail

Let $N_{\mathrm{△}}(G)$ be the number of triangles in a graph $G$. In [14] and [25] (respectively) the following bounds were proved on the lower tail behaviour of triangle counts in the dense Erdős-Rényi random graphs $G_m\sim G(n,m)$: $$\mathbb{P}(N_{\mathrm{△}}(G_m)<(1-\delta )\mathbb{E}[N_{\mathrm{△}}(G_m)])=\exp (-\mathrm{\Theta }\left({\delta }^2{n}^3\right))\text{if }{n}^{-3\mathrm{/}2}\ll \delta \ll n^{-1}$$ and $$\mathbb{P}(N_{\mathrm{△}}(G_m)<(1-\delta )\mathbb{E}[N_{\mathrm{△}}(G_m)])=\exp (-\mathrm{\Theta }({\delta }^{2\mathrm{/}3}{n}^2))\text{if }{n}^{-3\mathrm{/}4}\ll \delta \ll 1\text{.}$$ Neeman, Radin and Sadun [25] also conjectured that the probability should be of the form $\exp (-\mathrm{\Theta }\left({\delta }^2{n}^3\right))$ in the “missing interval” $n^{-1}\ll \delta \ll n^{-3\mathrm{/}4}$. We prove this conjecture. As part of our proof we also prove that some random graph statistics, related to degrees and codegrees, are normally distributed with high probability.