The Probability of Non-Existence of a Subgraph in a Moderately Sparse Random Graph

We develop a general procedure that finds recursions for statistics counting isomorphic copies of a graph G₀ in the common random graph models (n,m) and (n,p). Our results apply when the average degrees of the random graphs are below the threshold at which each edge is included in a copy of G₀. This extends an argument given earlier by the second author for G₀=K₃ with a more restricted range of average degree. For all strictly balanced subgraphs G₀, our results give much information on the distribution of the number of copies of G₀ that are not in large 'clusters' of copies. The probability that a random graph in (n,p) has no copies of G₀ is shown to be given asymptotically by the exponential of a power series in n and p, over a fairly wide range of p. A corresponding result is also given for (n,m), which gives an asymptotic formula for the number of graphs with n vertices, m edges and no copies of G₀, for the applicable range of m. An example is given, computing the asymptotic probability that a random graph has no triangles for p=o(n^-7/11) in (n,p) and for m=o(n^15/11) in (n,m), extending results of the second author.