Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph : The Lower Tail
arXiv:2403.13792 · doi:10.1016/j.ejc.2025.104189
Abstract
Let be the number of triangles in a graph . 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 : \[ \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 } \] 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 .} \] Neeman, Radin and Sadun [25] also conjectured that the probability should be of the form in the "missing interval" . 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 (6)
- Upper tails and independence polynomials in random graphs
- On the variational problem for upper tails in sparse random graphs
- Moderate deviations via cumulants
- The lower tail: Poisson approximation revisited
- On the lower tail variational problem for random graphs
- Lower tails for triangles inside the critical window