Cliques in random graphs
- 1 September 1976
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Proceedings of the Cambridge Philosophical Society
- Vol. 80 (3), 419-427
- https://doi.org/10.1017/s0305004100053056
Abstract
Let 0 < p < 1 be fixed and denote by G a random graph with point set , the set of natural numbers, such that each edge occurs with probability p, independently of all other edges. In other words the random variables eij, 1 ≤ i < j, defined byare independent r.v.'s with P(eij = 1) = p, P(eij = 0) = 1 − p. Denote by Gn the subgraph of G spanned by the points 1, 2, …, n. These random graphs G, Gn will be investigated throughout the note. As in (1), denote by Kr a complete graph with r points and denote by kr(H) the number of Kr's in a graph H. A maximal complete subgraph is called a clique. In (1) one of us estimated the minimum of kr(H) provided H has n points and m edges. In this note we shall look at the random variablesthe number of Kr's in Gn, andthe maximal size of a clique in Gn.Keywords
This publication has 3 references indexed in Scilit:
- On the evolution of random graphsPublished by Walter de Gruyter GmbH ,2011
- On complete subgraphs of different ordersMathematical Proceedings of the Cambridge Philosophical Society, 1976
- On colouring random graphsMathematical Proceedings of the Cambridge Philosophical Society, 1975