A limit theorem for small cliques in inhomogeneous random graphs

Abstrakt

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, based on the projection method. In addition to providing alternative proofs, our approach makes direct links to the theory of graphons.