The lower tail of triangle counts in sparse random graphs
Abstract
Let Tn be the number of triangles in the Erdős-Rényi random graph G(n,p) with n−1/2≪ p≪1 and fix η∈(0,1). We study the large deviation rate of the lower tail event Tn≤η𝔼[Tn], and the typical structure of G(n,p) conditioned on this event. By earlier work [16,19,21,49], both the rate and the structure are governed by a variational problem over graphons. In this work we solve this variational problem for every η∈(0,1). We show that every minimizer is either a constant graphon or a step graphon with two blocks of equal size. Correspondingly, the conditioned graph is close to an Erdős-Rényi graph or to a symmetric stochastic block model with two blocks. These two regimes are separated by a first order phase transition at the threshold η*=0.009217…. This resolves a conjecture of Zhao [78] and an open problem of Janson and Warnke [39] on triangles. It thereby gives a complete description of the lower tail of triangle counts in this range of p.
Related
- Upper tail large deviations of regular subgraph counts in sparse random regular graphs
- A first order phase transition for lower tails in sparse random graphs
- When are random regular triangle-free graphs bipartite?
- Sparse chromatic graphs and the complete-graph triangle bound
- Sparse Approximate Chromatic Profiles of Triangle-Free Graphs
BibTeX
@misc{huang2026lower,
title = {{The lower tail of triangle counts in sparse random graphs}},
author = {Dong Huang and Shuangping Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32879},
eprint = {2610.32879},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32879},
}
RIS
TY - UNPB
TI - The lower tail of triangle counts in sparse random graphs
AU - Dong Huang
AU - Shuangping Li
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32879
UR - https://arxiv.org/abs/2610.32879
AB - Let T_n be the number of triangles in the Erdős-Rényi random graph G(n,p) with n^−1/2≪ p≪1 and fix η∈(0,1). We study the large deviation rate of the lower tail event T_n≤η𝔼[T_n], and the typical structure of G(n,p) conditioned on this event. By earlier work [16,19,21,49], both the rate and the structure are governed by a variational problem over graphons. In this work we solve this variational problem for every η∈(0,1). We show that every minimizer is either a constant graphon or a step graphon with two blocks of equal size. Correspondingly, the conditioned graph is close to an Erdős-Rényi graph or to a symmetric stochastic block model with two blocks. These two regimes are separated by a first order phase transition at the threshold η_*=0.009217…. This resolves a conjecture of Zhao [78] and an open problem of Janson and Warnke [39] on triangles. It thereby gives a complete description of the lower tail of triangle counts in this range of p.
ER -