Local central limit theorem for triangle counts in sparse random graphs

Abstract

Let $X_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 $X_H$ as long as $H$ is connected, $p\gg n^{-1/m(H)}$ and $n^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\in (4n^{-1/2},1/2)$, then $$\underset{x\in \mathcal{L}}{\sup }\left|\frac{1}{\sqrt{2\ddot{I}€}}{e}^{-x^2/2}-\ddot{I}ƒ\cdot \mathbb{P}(X^{\ast }=x)\right|=n^{-1/2+o(1)}{p}^{1/2},$$ where $\ddot{I}{ƒ}^2=\mathbb{V}\text{ar}(X_{K_3})$, $X^{\ast }=(X_{K_3}-\mathbb{E}(X_{K_3}))/\ddot{I}ƒ$ and $\mathcal{L}$ is the support of $X^{\ast }$. 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}\ll p<c$, for any constant $c\in (0,1)$. Our quantitative result is enough to prove that the triangle counts converge to an associated normal distribution also in the ${\ell }_1$-distance. This is the first local central limit theorem for subgraph counts above the so-called $m_2$-density threshold.

17 pages