A limit theorem for small cliques in inhomogeneous random graphs

Abstract

The theory of graphons comes with a natural sampling procedure, which results in an inhomogeneous variant of the Erdős--Rényi random graph, called $W$-random graphs. We prove, via the method of moments, a limit theorem for the number of $r$-cliques in such random graphs. We show that, whereas in the case of dense Erdős--Rényi random graphs the fluctuations are normal of order $n^{r-1}$, the fluctuations in the setting of $W$-random graphs may be of order $0,n^{r-1}$, or $n^{r-0.5}$. Furthermore, when the fluctuations are of order $n^{r-0.5}$ they are normal, while when the fluctuations are of order $n^{r-1}$ they exhibit either normal or a particular type of chi-square behavior whose parameters relate to spectral properties of $W$. These results can also be deduced from a general setting [Janson and Nowicki, PTRF 1991], based on the projection method. In addition to providing alternative proofs, our approach makes direct links to the theory of graphons.

22 pages, 3 figures; accepted to Journal of Graph Theory