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

Abstract

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ős-Rényi random graphs $G_m\sim G(n,m)$: \[ \mathbb{P}\big(N_{\triangle}(G_m) \, < \, (1-δ)\mathbb{E}[N_{\triangle}(G_m)]\big) \,=\, \exp\left(-Θ\left(δ^2n^3\right)\right) \qquad \text{if $n^{-3/2}\ll \delta \ll n^{-1}$} \] and \[ \mathbb{P}\big(N_{\triangle}(G_m) \, < \, (1-δ)\mathbb{E}[N_{\triangle}(G_m)]\big) \,=\, \exp\left(-Θ(δ^{2/3}n^2) \right) \qquad \text{if $n^{-3/4}\ll \delta \ll 1$.} \] Neeman, Radin and Sadun [25] also conjectured that the probability should be of the form $\exp \left(-\Theta \left({\delta }^2{n}^3\right)\right)$ in the "missing interval" $n^{-1}\ll \delta \ll 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.

References in corpus (1)

• Lower tails for triangles inside the critical window