##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 163.18203

**Autor: ** Erdös, Pál

**Title: ** On cliques in graphs (In English)

**Source: ** Isr. J. Math. 4, 233-234 (1966).

**Review: ** A complete subgraph of a graph G is called a clique if it is not contained in any other complete subgraph of G. Let g(n) denote the maximum number of different sizes of cliques that can occur in a graph with n points: if log_{k} n denotes the k-times iterated logarithm to the base 2 of n, let H = H(n) be the smallest integer such that log_{H} n < 2. The author shows that g(n) \geq n- log n-H(n)-O(1). This extends an earlier result of the reviewer and *L.Moser* [Isr. J. Math. 3, 23-28 (1965; Zbl 144.23205)].

**Reviewer: ** J.W.Moon

**Classif.: ** * 05C35 Extremal problems (graph theory)

**Index Words: ** topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag