On the Number of Subgraphs of a Specified Form Embedded in a Random Graph

Let U₁, U₂,... be a sequence of i.i.d. random elements in R^d. For x>0, a graph G_n(x) may be formed by connecting with an edge each pair of points in that are separated by a distance no greater than x. The points of G_n(x) could represent the stations in a telecommunications network and the edge set the lines of communication that exist among them. Let be a collection of graphs on mn points having a specified form or structure, and let denote the number of subgraphs embedded in G_n(x) and contained in . It is shown that a SLLN, CLT and LIL for follow easily from the theory of U-statistics. In addition, a uniform (in x) SLLN is proved for collections that satisfy a certain monotonicity condition. Some applications are mentioned and the results of some simulations presented. The scaling constants appearing in the CLT are usually hard to obtain. These are worked out for some special cases.