Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-27T04:32:19.707Z Has data issue: false hasContentIssue false

Poisson convergence and random graphs

Published online by Cambridge University Press:  24 October 2008

A. D. Barbour
Affiliation:
Gonville and Gaius College, Cambridge

Extract

Approximation by the Poisson distribution arises naturally in the theory of random graphs, as in many other fields, when counting the number of occurrences of individually rare and unrelated events within a large ensemble. For example, one may be concerned with the number of times that a particular small configuration is repeated in a large graph, such questions being considered, amongst others, in the fundamental paper of Erdös and Rényi (4). The technique normally used to obtain such approximations in random graph theory is based on showing that the factorial moments of the quantity concerned converge to those of a Poisson distribution as the size of the graph tends to infinity. Since the rth factorial moment is just the expected number of ordered r-tuples of events occurring, it is particularly well suited to evaluation by combinatorial methods. Unfortunately, such a technique becomes very difficult to manage if the mean of the approximating Poisson distribution is itself increasing with the size of the graph, and this limits the scope of the results obtainable.

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1982

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Barbour, A. D. and Eagleson, G. K. Poisson approximation for some statistics based on exchangeable trials. (1982).CrossRefGoogle Scholar
(2)Bollobá;s, B.Threshold functions for small subgraphs. Math. Proc. Cambridge Phil. Soc. 90 (1981), 197206.CrossRefGoogle Scholar
(3)Chen, L. H. Y.Poisson approximation for dependent trials. Ann. Prob. 3 (1975), 534545.CrossRefGoogle Scholar
(4)Erdös, P. and Rényi, A.On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. V, (1960), 1761.Google Scholar
(5)Schürger, K.Limit theorems for complete subgraphs of random graphs. Period. Mat. Hung. 10 (1979), 4753.CrossRefGoogle Scholar
(6)Stein, C.A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. Proc. Vlth Berk. Symp. Math. Slat. Prob. 2 (1970), 583602.Google Scholar