A Local Central Limit Theorem for Clique Counts in Sparse Random Graphs

Abstract

Let $X_H$ denote the number of copies of a fixed graph $H$ in $G_{n,p}$. Gilmer and Kopparty conjectured that $X_H$ satisfies a local central limit theorem (LCLT) provided that $H$ is connected, $p\gg n^{-1/m(H)}$, and $n^2(1-p)\gg 1$, where $m(H)$ is the maximum density. Following the work of Berkowitz, Sah and Sawhney confirmed this conjecture for every constant $p$, leaving the regime where $p=o(1)$ open. In this regime, the only case addressed in the literature is when $H=K_3$, where, in a recent paper, Araújo and Mattos confirmed the conjecture for $p\in (4n^{-1/2},1/2)$. This, together with a general result of Röllin and Ross, essentially settles the conjecture for the triangle. We generalise these results by showing that an LCLT holds for $H=K_r$ (for any fixed $r\ge 3$) in the regime $n^{-1/m(H)}\ll p\le 1/2$, essentially settling the conjecture for cliques.

Comments are welcome!