The asymptotic distributions of generalized U-statistics with applications to random graphs (Q811004)

We consider the random variable \[ S_{n,\nu}(f)=\sum_{i_ 1<...<i_{\nu}\leq n}f(X_{i_ 1},...,X_{i_{\nu}},Y_{i_ 1i_ 2},...,Y_{i_{\nu -1}i_{\nu}}), \] where \(\{X_ i\}^ n_{i=1}\) and \(\{Y_{ij}\}_{1\leq i<j\leq n}\) are two independent sequences of i.i.d. random variables. This paper gives a general treatment of the asymptotic behaviour of sums of the form \(S_{n,\nu}(f)\). We use a projection method and expand f into a (finite) sum of terms of increasing complexity. The terms in such an expansion are indexed by graphs and the asymptotic behaviour of \(S_{n,\nu}\) depends only on the non-zero terms indexed by the smallest graphs. Moreover, the type of the limit distribution depends on the topology of the graphs. In particular, \(S_{n,\nu}(f)\) is asymptotically normally distributed if these graphs are connected, but not otherwise. The general theorems are applied to the problems of finding the asymptotic distribution of the number of copies or induced copies of a given graph in various random graph models.