Moderate deviation rates in sparse G(n,m)
Remark 1.2 (Open Problem on Sparse Densities) · arXiv:1902.06830
Status partial high confidence
The open problem of finding the asymptotic rate for moderate deviations of subgraph counts across the entire range of sparse densities in $G(n,m)$ and $G(n,p)$ remains open for general subgraphs. For triangle counts specifically, Alvarado, Gonçalves de Oliveira, and Griffiths (2023, published 2025) determined $\log\mathbb{P}(N_{\triangle}(G) > (1+\delta)p^3 n^3)$ up to a constant factor for densities above $n^{-1/2}(\log n)^{1/2}$, and also handled the lower tail for cherries. Alvarado, Dias, and Griffiths (2024, published 2025) further resolved the lower tail for triangle counts in $G(n,m)$ in the regime $n^{-1} \ll \delta \ll n^{-3/4}$. The full conjecture—covering all subgraphs and all sparse density regimes—remains open.
Cited literature (2)
-
partial Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs $G(n,m)$ and $G(n,p)$ (2023)
Determines $\log\mathbb{P}(N_{\triangle}(G) > (1+\delta)p^3 n^3)$ up to a constant factor for densities above $n^{-1/2}(\log n)^{1/2}$ in both $G(n,m)$ and $G(n,p)$, and achieves a $(1+o(1))$ factor in the non-localized regime of $G(n,p)$, making substantial partial progress on the sparse density open problem for triangle counts.
-
partial Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph $G(n,m)$: The Lower Tail (2024)
Proves the lower tail probability for triangle counts in $G(n,m)$ is $\exp(-\Theta(\delta^2 n^3))$ in the previously unresolved regime $n^{-1} \ll \delta \ll n^{-3/4}$, completing the picture for the lower tail of triangles in dense random graphs.
Reviewer notes. The open problem concerns all subgraphs across all sparse densities; the follow-up work focuses on triangles (and 2-paths) and specific density thresholds. The full problem remains open, but the triangle case has seen major partial progress in 2023–2024.
Context
Theorem 1.1 establishes the asymptotic rate for moderate deviations of subgraph counts in $G(n,m)$ when $t(n)$ is bounded away from 1, with a partial extension to sparser regimes satisfying $\max\{t^{1/2}n^{-1/2}\log n,\, t^{e-3/2}\} \ll \alpha_n \ll \min\{t^{2e-5/2}n^{1/2},\, t^{e+2}n^{1/2}\}$. The authors note they initially proved results only in the dense case $t\in(0,1)$ constant and have only partially extended to sparser regimes.
Notes. Stated in Remark 1.2 as an open problem in prose form, without a dedicated labeled theorem environment. PDF source — math notation in surrounding theorems may be partially garbled.
Source paper
Moderate deviations of subgraph counts in the Erdős-Rényi random graphs $G(n,m)$ and $G(n,p)$
Christina Goldschmidt, Simon Griffiths, Alex Scott · 2020-02-10
https://arxiv.org/abs/1902.06830
PDF source