The probability of non-existence of a subgraph in a moderately sparse random graph
Combinatorics, Probability and Computing
MetadataShow full item record
We develop a general procedure that finds recursions for statistics counting isomorphic copies of a graph G0 in the common random graph models G(n,m) and G(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 G0. This extends an argument given earlier by the second author for G0=K3 with a more restricted range of average degree. For all strictly balanced subgraphs G0, our results gives much information on the distribution of the number of copies of G0 that are not in large "clusters" of copies. The probability that a random graph in G(n,p) has no copies of G0 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 G(n,m), which gives an asymptotic formula for the number of graphs with n vertices, m edges and no copies of G0, 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 G(n,p) and for m=o(n15/11) in G(n,m), extending results of the second author.
- College Publications