Modular statistics for subgraph counts in sparse random graphs

Abstract

Answering a question of Kolaitis and Kopparty, we show that, for given integer $q>1$ and pairwise nonisomorphic connected graphs $G_1...G_k$, if $p=p(n)$ is such that $\mathrm{Pr}(G_{n,p}\supseteq G_i)\to 1$ $\forall i$, then, with ${\xi }_i$ the number of copies of $G_i$ in $G_{n,p}$, $({\xi }_1...{\xi }_k)$ is asymptotically uniformly distributed on ${\mathbf{Z}}_q^k$.