Hostname: page-component-7b7567c8c-m6dxt Total loading time: 0 Render date: 2026-11-18T14:24:22.722Z Has data issue: false hasContentIssue false

Cliques in random graphs

Published online by Cambridge University Press:  24 October 2008

B. Bollobas
Affiliation:
University of Cambridge
P. Erdös
Affiliation:
University of 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.

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 by

are 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 variables

the number of Kr's in Gn, and

the maximal size of a clique in Gn.

Information

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1976