Large-Deviation Asymptotics for Triangle Counts

Definitions and mathematical statement

Let $n\geq 3$ be an integer and $p\in[0,1]$. The binomial random graph $G_{n,p}$ has vertex set $\{1,\ldots,n\}$, with each unordered pair of distinct vertices present as an edge independently with probability $p$. Its triangle count is \[ X=X_{n,p}=\sum_{1\leq i<j<k\leq n}\mathbf{1}_{\{\{i,j\},\{i,k\},\{j,k\}\in E(G_{n,p})\}}, \qquad \mu_{n,p}=\mathbb{E}X_{n,p}=\binom{n}{3}p^3. \] For a real deviation parameter $\delta$, define the logarithmic lower-tail quantity \[ L_n(p,\delta)=-\log\Pr\!\left(X_{n,p}\leq(1-\delta)\mu_{n,p}\right), \] where $\log$ is the natural logarithm and $-\log 0=+\infty$. Allowing real $\delta$ here defines the expression; it does not resolve the intended deviation range of the source problem.

The supplied corrected statement asks for the asymptotic behavior of $L_n(p_n,\delta)$ as $n\to\infty$ throughout the remaining unresolved sparse regimes, particularly \[ p_n=O(n^{-1/2}). \] The original statement explicitly includes sparse sequences $p_n\to0$. The source does not specify the range of $\delta$, whether it is fixed or may vary with $n$, the precise collection of unresolved parameter regimes, or whether the requested asymptotics mean an asymptotic equivalent, a limiting normalized rate, or matching bounds. Thus this is an asymptotic determination problem whose full quantifiers require clarification; no particular normalization or universal asymptotic formula is asserted here.

The original supplied statement also asks for the upper-tail quantity \[ U_n(p,\delta)=-\log\Pr\!\left(X_{n,p}\geq(1+\delta)\mu_{n,p}\right). \] The corrected statement retains only the lower-tail target. This difference in scope remains unresolved: the upper-tail request is preserved as source history, without asserting that it remains part of the intended current problem. The source also supplies no boundary exclusions or separate treatment of $p=0$, $p=1$, or deviation endpoints.

Short English statement

Determine the leading logarithmic probability that a binomial random graph has fewer triangles than its expectation by the prescribed relative deviation, especially when $p=O(n^{-1/2})$. The deviation range and the required precision of the asymptotics are unspecified. The original record also requests upper-tail asymptotics, whereas the corrected statement requests only lower tails.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004131$, title Large-Deviation Asymptotics for Triangle Counts, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The proposed year is recorded as 2019; no individual proposer is identified.
• Supplied report citation: Combinatorics, Probability and Computing (2020), Oberwolfach Reports, DOI 10.4171/owr/2019/19, pp. 1113--1189. The literature list labels this source Oberwolfach Report 19/2019, triangle lower tails. https://doi.org/10.4171/owr/2019/19. The background describes these reports as records of mathematical workshops and their open-problem discussions.
• Jenssen--Perkins--Potukuchi--Simkin, Lower tails for triangles inside the critical window. https://arxiv.org/abs/2411.18563.
• Supplied literature assessment checked on 2026-08-22: status recorded as open; dense and off-critical regimes described as understood; substantial new partial results described for the critical window; general triangle lower-tail logarithmic asymptotics described as unresolved. This is supplied dated curation derived from the OWR material, not independently verified here. The record expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that the official Oberwolfach report was checked directly, with definitions restored and source-dependent wording removed. These are supplied verification claims, not verification performed for this draft.