Hostname: page-component-8448b6f56d-gtxcr Total loading time: 0 Render date: 2024-04-23T21:31:39.777Z Has data issue: false hasContentIssue false
  • English
  • Français

Threshold functions for small subgraphs

Published online by Cambridge University Press:  24 October 2008

Béla Bollobás
Béla Bollobás
Affiliation:
Trinity College, Cambridge
Get access Rights & Permissions [Opens in a new window]

Extract

In this note we shall study random labelled graphs. Denote by

the set of all graphs with n given labelled vertices and M(n) edges. As usual, we turn (M(n)) into a probability space by giving all graphs the same probability. The question we address ourselves to is the following. Given a graph H and a constant p, 0 < p < 1, for what functions M(n) is it true that the probability PM(n)(H ⊂ G) that a graph G∈ (M(n)) contains H tends to p as n∞→? This question was posed by Erdös and Rényi (3), (4), who also proved several beautiful and surprising theorems. In order to state the main general result of Erdös and Rényi in this direction, and for our use later, we introduce some definitions.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 90 , Issue 2 , September 1981 , pp. 197 - 206
Copyright
Copyright © Cambridge Philosophical Society 1981

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)Bollobás, B.Graph theory – An introductory course, Graduate Texts in Mathematics, vol. 63 (Springer-Verlag, New York, Heidelberg, Berlin, 1979).Google Scholar
(2)Chung, K. L.A course in probability theory, 2nd ed. (Academic Press, New York, London, 1974).Google Scholar
(3)Erdös, P. and Rényi, A.On random graphs, I. Publ. Math. Debrecen 6 (1959), 290–297.CrossRefGoogle Scholar
(4)Erdös, P. and Rényi, A.On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17–61.Google Scholar
(5)Feller, W.An introduction to probability theory and its applications, vol. I, 3rd ed. (New York, 1974).Google Scholar
(6)Schürger, K.Limit theorems for complete subgraphs of random graphs, Per. Math. Hungar. 10 (1979), 47–53.CrossRefGoogle Scholar