2016/08/18 by Dudley Stark, Stark, Dudley, Nick Wormald +1
Mathematics · #05A16 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #math.CO #msc:05A16 #msc:05C80
paper · pdf · doi:10.48550/arxiv.1608.05193
44 pages
arxiv created 2016/08/18 · openalex publication_date 2016/08/18 · arxiv updated 2016/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop a general procedure that finds recursions for statistics counting isomorphic copies of a graph G0 in the common random graph models \cal G(n,m) and \cal 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 \cal 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 \cal 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 \cal G(n,p) and for m=o(n15/11) in \cal G(n,m), extending results of the second author.