Premium
The perturbation method and triangle‐free random graphs
Author(s) -
Wormald Nicholas C.
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199608/09)9:1/2<253::aid-rsa15>3.0.co;2-o
Subject(s) - mathematics , random variable , poisson distribution , random graph , combinatorics , probability generating function , discrete mathematics , graph , statistics , probability mass function
When a discrete random variable in a discrete space is asymptotically Poisson, there is often a powerful method of estimating its distribution, by calculating the ratio of the probabilities of adjacent values of the variable. The versatility of this method is demonstrated by finding asymptotically the probability that a random graph has no triangles, provided the edge density is not too large. In particular, the probability that G ϵ G( n, p ) has no triangles is asymptotic to $\exp(-{1 \over 6}p^3n^3+{1 \over 4}p^5n^4-{7 \over 12}p^7n^5) \hbox{ for } p=o(n^{-2/3})$ , and for G ϵ G( n, m ) it is asymptotic to $\exp(-{1 \over 6}d^3n^3) \hbox{ for } d={{2m}\over{n(n-1)}}=o(n^{-2/3})$ . © 1996 John Wiley & Sons, Inc.