The probability of non-existence of a subgraph in a moderately sparse random graph

Abstract: We develop a general procedure that finds recursions for statistics counting isomorphic copies of a graph

G_{0}

in the common random graph models

c a l G (n, m)

and

c a l 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

G_{0}

. This extends an argument given earlier by the second author for

G_{0} = K_{3}

with a more restricted range of average degree. For all strictly balanced subgraphs

G_{0}

, our results gives much information on the distribution of the number of copies of

G_{0}

that are not in large "clusters" of copies. The probability that a random graph in

c a l G (n, p)

has no copies of

G_{0}

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

c a l G (n, m)

, which gives an asymptotic formula for the number of graphs with

n

vertices,

m

edges and no copies of

G_{0}

, 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

c a l G (n, p)

and for

m = o (n^{15 / 11})

in

c a l G (n, m)

, extending results of the second author.

Recommendations

Cites Work

Cited In (5)

This page was built for publication: The probability of non-existence of a subgraph in a moderately sparse random graph