Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T06:16:30.840Z Has data issue: false hasContentIssue false

Threshold functions for small subgraphs

Published online by Cambridge University Press:  24 October 2008

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

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1981