← All problems

Lower tail of triangle counts in sparse random graphs

Let G(n,p)G(n,p) be an Erdős–Rényi random graph, let TnT_n denote its number of triangles, and suppose that n−1/2≪p≪1n^{-1/2}\ll p\ll 1. For each fixed η∈(0,1)\eta\in(0,1), determine the large-deviation rate of P ⁣(Tn≤η E[Tn])\mathbb{P}\!\bigl(T_n\leq \eta\,\mathbb{E}[T_n]\bigr) and characterize the typical structure of G(n,p)G(n,p) conditioned on the event Tn≤η E[Tn]T_n\leq \eta\,\mathbb{E}[T_n]. Equivalently, solve the associated graphon variational problem and classify its minimizers for every η∈(0,1)\eta\in(0,1).

References

Source: arXiv

Progress summary

Refreshed
Open

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 n−1/2≪p≪1n^{-1/2}\ll p\ll 1.

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 0.4660.466 and 0.2090.209; these results do not classify all minimizers.
  • Critical-window work: for p=cn−1/2p=cn^{-1/2}, 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.

Sources

Solutions 0

No solutions have been posted yet.