Local central limit theorem for triangle counts in sparse random graphs

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 $\sup_{x\in \mathcal{L}}\left| \dfrac{1}{\sqrt{2π}}e^{-x^2/2}-σ\cdot \mathbb{P}(X^* = x)\right|=n^{-1/2+o(1)}p^{1/2},$ where $σ^2 = \mathbb{V}\text{ar}(X_{K_3})$, $X^{*}=(X_{K_3}-\mathbb{E}(X_{K_3}))/σ$ and $\mathcal{L}$ is the support of $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}\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.

No reviews yet.

No comments yet.