Threshold functions for small subgraphs
- 1 September 1981
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Proceedings of the Cambridge Philosophical Society
- Vol. 90 (2) , 197-206
- https://doi.org/10.1017/s0305004100058655
Abstract
In this note we shall study random labelled graphs. Denote by the set of all graphs with n given labelled vertices andM(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 graphHand a constant p, 0 < p < 1, for what functionsM(n)is it true that the probability PM(n)(H ⊂ G) that a graphG∈(M(n))containsHtends topas 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.Keywords
This publication has 3 references indexed in Scilit:
- On random graphs. I.Publicationes Mathematicae Debrecen, 2022
- On the evolution of random graphsPublished by Walter de Gruyter GmbH ,2011
- Limit theorems for complete subgraphs of random graphsPeriodica Mathematica Hungarica, 1979