A limit theorem for small cliques in inhomogeneous random graphs
Jan Hladký, Christos Pelekis, Matas Šileikis
Abstract
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 ‐random graphs. We prove, via the method of moments, a limit theorem for the number of ‐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 , the fluctuations in the setting of ‐random graphs may be of order , or . Furthermore, when the fluctuations are of order they are normal, while when the fluctuations are of order they exhibit either normal or a particular type of chi‐square behavior whose parameters relate to spectral properties of . 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.