Threshold functions for small subgraphs

Abstract

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 P M(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.