Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-13T00:58:10.804Z Has data issue: false hasContentIssue false
  • English
  • Français

Cliques in random graphs

Published online by Cambridge University Press:  24 October 2008

B. Bollobas  and
P. Erdös
B. Bollobas
Affiliation:
University of Cambridge
P. Erdös
Affiliation:
University of Cambridge
Get access Rights & Permissions [Opens in a new window]

Extract

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.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 80 , Issue 3 , November 1976 , pp. 419 - 427
Copyright
Copyright © Cambridge Philosophical Society 1976

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Bollobás, B.On complete subgraphs of different orders. Math. Proc. Cambridge Philos. Soc. 79 (1976), 19–24.CrossRefGoogle Scholar
(2)Erdös, P. and Rényi, A.On the evolution of random graphs. Publ. Math. Inst. Hung. A. Sci. 5 A (1960), 17–61.Google Scholar
(3)Grimmett, G. R. and McDiarmid, C. J. H.On colouring random graphs. Math. Proc. Cambridge Philos. Soc. 77 (1975), 313–324.CrossRefGoogle Scholar
(4)Matula, D. W. On the complete subgraphs of a random graph. Combinatory Mathematics and its Applications (Chapel Hill, N.C., 1970), 356–369.Google Scholar
(5)Matula, D. W. The employee party problem. (To appear.)Google Scholar