Local large deviations for triangles in sparse random graphs
Abstract
We revisit a classic topic in probabilistic combinatorics, the lower-tail large-deviation problem for triangles in the random graph G(n,p). Here we aim for first-order asymptotics for the quantity ℙ[X=k] with X the number of triangles in G(n,p) and 0 ≤ k ≤ (1−ε) 𝔼X, in the sparse regime in which the logarithmic asymptotics are Poissonian. When k=0 (the case of triangle-freeness) and p = p(n) is sufficiently small, first-order asymptotics are known via Janson's inequality and results of Stark and Wormald; when k is sufficiently close to 𝔼X, first-order asymptotics are known via local central limit theorems. Our main result gives first-order asymptotics for all k in the above range when p = o(n−2/3), improving upon the result of Frieze that required p = o(n−4/5). We also characterize, up to vanishing total variation distance, the distribution of the k triangles in the corresponding conditional distribution and give an efficient algorithm to approximately sample from this conditional distribution. Notably, when k = Θ(μ) there is a transition at p = Θ(n−4/5) from an asymptotically uniform triangle distribution to a distribution asymptotically singular to uniform.
Related
- Upper tail large deviations of regular subgraph counts in sparse random regular graphs
- Local Convergence of Triadic Closures of Sparse Random Graphs
- Optimal path decompositions of sparse random graphs
- Coloring sparse random Cayley graphs
- A first order phase transition for lower tails in sparse random graphs
BibTeX
@misc{lintott2026local,
title = {{Local large deviations for triangles in sparse random graphs}},
author = {Jade Lintott and Will Perkins and Corrine Yap},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21890},
eprint = {2609.21890},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21890},
}
RIS
TY - UNPB
TI - Local large deviations for triangles in sparse random graphs
AU - Jade Lintott
AU - Will Perkins
AU - Corrine Yap
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21890
UR - https://arxiv.org/abs/2609.21890
AB - We revisit a classic topic in probabilistic combinatorics, the lower-tail large-deviation problem for triangles in the random graph G(n,p). Here we aim for first-order asymptotics for the quantity ℙ[X=k] with X the number of triangles in G(n,p) and 0 ≤ k ≤ (1−ε) 𝔼X, in the sparse regime in which the logarithmic asymptotics are Poissonian. When k=0 (the case of triangle-freeness) and p = p(n) is sufficiently small, first-order asymptotics are known via Janson's inequality and results of Stark and Wormald; when k is sufficiently close to 𝔼X, first-order asymptotics are known via local central limit theorems. Our main result gives first-order asymptotics for all k in the above range when p = o(n^−2/3), improving upon the result of Frieze that required p = o(n^−4/5). We also characterize, up to vanishing total variation distance, the distribution of the k triangles in the corresponding conditional distribution and give an efficient algorithm to approximately sample from this conditional distribution. Notably, when k = Θ(μ) there is a transition at p = Θ(n^−4/5) from an asymptotically uniform triangle distribution to a distribution asymptotically singular to uniform.
ER -