Lower tail of triangle counts in sparse random graphs
Let be an Erdős–Rényi random graph, let denote its number of triangles, and suppose that . For each fixed , determine the large-deviation rate of and characterize the typical structure of conditioned on the event . Equivalently, solve the associated graphon variational problem and classify its minimizers for every .
References
- The lower tail of triangle counts in sparse random graphs — arXiv — Dong Huang, Shuangping Li
Source: arXiv
Progress summary
The general sparse-graph triangle lower-tail problem remains open; earlier work gives only partial variational results.
The problem seeks a complete large-deviation rate and conditional graph structure for unusually few triangles in sparse random graphs, throughout the regime .
Known results
- Zhao and related work: the constant graphon is minimizing in a replica-symmetric range, but not in another range.
- 2015 variational work: for triangles, approximate sparse-limit thresholds are and ; these results do not classify all minimizers.
- Critical-window work: for , first-order asymptotics and conditional structure are known in restricted parameter ranges.
Current status (as of October 2026): the complete problem remains open, with only partial variational and critical-window results publicly established.
Solutions 0
No solutions have been posted yet.