Fluctuations of Subgraph Counts in Graphon Based Random Graphs

Abstract

Given a graphon $W$ and a finite simple graph $H$, with vertex set $V(H)$, denote by $X_n(H,W)$ the number of copies of $H$ in a $W$-random graph on $n$ vertices. The asymptotic distribution of $X_n(H,W)$ was recently obtained by Hladký, Pelekis, and Šileikis (2021) in the case where $H$ is a clique. In this paper, we extend this result to any fixed graph $H$. Towards this we introduce a notion of $H$-regularity of graphons and show that if the graphon $W$ is not $H$-regular, then $X_n(H,W)$ has Gaussian fluctuations with scaling $n^{|V(H)|-\frac{1}{2}}$. On the other hand, if $W$ is $H$-regular, then the fluctuations are of order $n^{|V(H)|-1}$ and the limiting distribution of $X_n(H,W)$ can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centered chi-squared random variables with the weights determined by the spectral properties of a graphon derived from $W$. Our proofs use the asymptotic theory of generalized $U$-statistics developed by Janson and Nowicki (1991). We also investigate the structure of $H$-regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also $H$-regular graphons $W$ for which both the Gaussian or the non-Gaussian components are degenerate, that is, $X_n(H,W)$ has a degenerate limit even under the scaling $n^{|V(H)|-1}$. We give an example of this degeneracy with $H=K_{1,3}$ (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher-order degeneracies.

arXiv comment36 pages, 6 figures. Major updates. Svante Janson joins as co-author. New results on higher-order limits and degeneracies added