## 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 Kd(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)n2/2, then every G(n,m) contains a Kd+1(t), where

t = [{\alpha log n \over d log (1/c)} ].     (1)

(b) Given an integer d \geq 1 there exists a constant \epsilond > 0 such that if 0 < c < \epsilond and n \geq n(d,c) is an integer then there exists a graph G(n,m) satisfying (1) which does not contain a Kd+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