Moderate Deviations of Triangle Counts in the Erd{o}s-R\'enyi Random Graph $G(n,m)$: The Lower Tail

Let N_(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{o}s-R\'enyi random graphs Gₘ~ G(n,m): \[ P(N_{}(G_m) \, < \, (1-δ)E[N_{}(G_m)]) \,=\, exp(-Θ(δ^2n^3)) if n-3/2 δ n⁻¹ \] and \[ P(N_{}(G_m) \, < \, (1-δ)E[N_{}(G_m)]) \,=\, exp(-Θ(δ2/3n^2) ) if n-3/4 δ 1. \] Neeman, Radin and Sadun [25] also conjectured that the probability should be of the form exp(-Θ(δ²n³)) in the "missing interval" n⁻¹ δ n-3/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.