Local central limit theorem for triangle counts in sparse random graphs
Let XHXHX_H be the number of copies of a fixed graph H in G(n,p). In 2016, Gilmer and Kopparty conjectured that a local central limit theorem should hold for XHXHX_H as long as H is connected, p≫n−1/m(H)p≫n−1/m(H)p\gg n^{-1/m(H)} and n2(1−p)≫1n2(1−p)≫1n^2(1-p)\gg 1, where m(H) denotes the m-density...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
March 2026
|
| In: |
Mathematical proceedings of the Cambridge Philosophical Society
Year: 2026, Jahrgang: 180, Heft: 2, Pages: 459-475 |
| ISSN: | 1469-8064 |
| DOI: | 10.1017/S0305004125101345 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1017/S0305004125101345 Verlag, lizenzpflichtig, Volltext: https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/local-central-limit-theorem-for-triangle-counts-in-sparse-random-graphs/BF46AAAEAD921D72294CAD42DC433AA8 
|
| Verfasserangaben: | By Pedro Araújo and Letícia Mattos |
| Zusammenfassung: | Let XHXHX_H be the number of copies of a fixed graph H in G(n,p). In 2016, Gilmer and Kopparty conjectured that a local central limit theorem should hold for XHXHX_H as long as H is connected, p≫n−1/m(H)p≫n−1/m(H)p\gg n^{-1/m(H)} and n2(1−p)≫1n2(1−p)≫1n^2(1-p)\gg 1, where m(H) denotes the m-density of H. Recently, Sah and Sawhney showed that the Gilmer-Kopparty conjecture holds for constant p. In this paper, we show that the Gilmer-Kopparty conjecture holds for triangle counts in the sparse range. More precisely, if p∈(4n−1/2,1/2)p∈(4n−1/2,1/2)p \in (4n^{-1/2}, 1/2), then supx∈L∣∣∣12π−−√e−x2/2−σ⋅P(X∗=x)∣∣∣=n−1/2+o(1)p1/2,supx∈L|12πe−x2/2−σ⋅P(X∗=x)|=n−1/2+o(1)p1/2, {} {} {}\sup_{x\in \mathcal{L}}\left| \dfrac{1}{\sqrt{2\pi}}e^{-x^2/2}-\sigma\cdot \mathbb{P}(X^* = x)\right|=n^{-1/2+o(1)}p^{1/2}, {} {}where σ2=Var(XK3)σ2=Var(XK3)\sigma^2 = \mathbb{V}\text{ar}(X_{K_3}), X∗=(XK3−E(XK3))/σX∗=(XK3−E(XK3))/σX^{*}=(X_{K_3}-\mathbb{E}(X_{K_3}))/\sigma and LL\mathcal{L} is the support of X∗X∗X^*. By combining our result with the results of Röllin-Ross and Gilmer-Kopparty, this establishes the Gilmer-Kopparty conjecture for triangle counts for n−1≪p<cn−1≪p<cn^{-1}\ll p \lt c, for any constant c∈(0,1)c∈(0,1)c\in (0,1). Our quantitative result is enough to prove that the triangle counts converge to an associated normal distribution also in the ℓ1ℓ1\ell_1-distance. This is the first local central limit theorem for subgraph counts above the so-called m2m2m_2-density threshold. |
|---|---|
| Beschreibung: | Online verfügbar: 14. November 2025 Gesehen am 13.02.2026 |
| Beschreibung: | Online Resource |
| ISSN: | 1469-8064 |
| DOI: | 10.1017/S0305004125101345 |