Let H be a fixed connected graph, let G_n,p be the Erdős–Rényi random graph, and let X_H denote the number of copies of H in G_n,p. Define m(H)=maxe(J)/(v(J)-1):J⊆ H, v(J)≥ 2. If p=p(n) satisfies p≫ n^-1/m(H) and n^2(1-p)≫ 1, then X_H satisfies a local central limit theorem: writing mu_n=EX_H, sigma_n^2=operatornameVar(X_H), and phi(x)=(2 pi)^-1/2e^-x^2/2, one has sup_k∈Z|sigma_n Pr(X_H=k)-phi((k-mu_n)/sigma_n)|→ 0 as n→∞.

Gilmer–Kopparty local central limit theorem conjecture

Let $H$ be a fixed connected graph, let $G_{n,p}$ be the Erdős–Rényi random graph, and let $X_H$ denote the number of copies of $H$ in $G_{n,p}$ . Define $m(H)=\max\{e(J)/(v(J)-1):J\subseteq H,\ v(J)\ge 2\}$ . If $p=p(n)$ satisfies $p\gg n^{-1/m(H)}$ and $n^2(1-p)\gg 1$ , then $X_H$ satisfies a local central limit theorem: writing $\mu_n=\mathbb{E}X_H$ , $\sigma_n^2=\operatorname{Var}(X_H)$ , and $\phi(x)=(2\pi)^{-1/2}e^{-x^2/2}$ , one has $\sup_{k\in\mathbb{Z}}\left|\sigma_n\Pr(X_H=k)-\phi\left((k-\mu_n)/\sigma_n\right)\right|\to 0$ as $n\to\infty$ .

Progress summary

Partially solved

A new preprint settles the conjecture for every fixed clique in a broad sparse range, but the version for all connected graphs remains open.

Introduced by Justin Gilmer and Swastik Kopparty in 2016, the conjecture predicts a local normal approximation for copies of any fixed connected graph in a random graph when $p\gg n^{-1/m(H)}$ and $n^2(1-p)\gg 1$ .

Known results

Röllin–Ross (2016): triangles for $n^{-1}\ll p=O(n^{-1/2})$ .
Gilmer–Kopparty (2016): triangles for fixed $p\in(0,1)$ .
Sah–Sawhney: every connected $H$ for constant $p$ .
Berkowitz (2018): fixed-clique counts for constant $p$ .

August 2026 sparse-clique theorem

Asaf Cohen Antonir, Ilay Hoshen, and Maksim Zhukovskii report a proof for every fixed clique $H=K_r$ , $r\ge 3$ , throughout $n^{-1/m(K_r)}\ll p\le \frac12$ . The arbitrary connected-graph conjecture remains open in the sparse regime.

Current status (as of August 2026): The conjecture is established for fixed cliques in the stated sparse range, and for broader graph classes in dense regimes, but remains open for arbitrary connected graphs in general sparse regimes.

Sources

Sources & referencesView supporting material

Primary source

arXiv

Additional references

A Local Central Limit Theorem for Clique Counts in Sparse Random Graphs — arXiv — Asaf Cohen Antonir, Ilay Hoshen, Maksim Zhukovskii

probability random-graphs

1 day ago