##
**Zentralblatt MATH**

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

**Zbl.No: ** 318.05110

**Autor: ** Bollobás, Béla; Erdös, Paul; Simonovits, M.

**Title: ** On the structure of edge graphs. II. (In English)

**Source: ** J. London Math. Soc., II. Ser. 12, 219-224 (1976).

**Review: ** Denote by G(n,m) a graph with n vertices and m edges and by K_{d}(t) the complete d-partite graph with t vertices in all classes. The following theorem is proved: (a) There is an absolute constant \alpha > 0 such that if 0 < c < 1/d and m > (1-1/d+c)n^{2}/2, then every G(n,m) contains a K_{d+1}(t), where t = **[**{\alpha log n \over d log (1/c)} **]**. (1) (b) Given an integer d \geq 1 there exists a constant \epsilon_{d} > 0 such that if 0 < c < \epsilon_{d} and n \geq n(d,c) is an integer then there exists a graph G(n,m) satisfying (1) which does not contain a K_{d+1}(t) with

t = **[**5{log n \over log (1/c)} **]**. This is a sequel to the article of *B. Bollobás* and *P. Erdös* in Bull. London math. Soc. 5, 317-321 (1973; Zbl 277.05135).

**Reviewer: ** St.Znám

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

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag