Modular statistics for subgraph counts in sparse random graphs (Q2256135)

Summary: Answering a question of \textit{P. G. Kolaitis} and \textit{S. Kopparty} [J. ACM 60, No. 5, Paper No. 8, 34 p. (2013; Zbl 1280.03040)], we show that, for given integer \(q>1\) and pairwise nonisomorphic connected graphs \(G_1,\dots, G_k\), if \(p=p(n) \) is such that \(\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,\dots, \xi_k)\) is asymptotically uniformly distributed on \(\mathbb Z_q^k\).