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