## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  491.05038
Autor:  Ajtai, M.; Erdös, Paul; Komlos, J.; Szemeredi, E.
Title:  On Turan's theorem for sparse graphs. (In English)
Source:  Combinatorica 1, 313-317 (1981).
Review:  Let \alpha be the (vertex) independence number and let log x = max{1,\ell nx}. Denote by f(n,t,p) the largest integer such that every graph of order n and average degree t \geq 1 that contains no Kp satisfies \alpha \geq f(n,t,p). Theorem: There exists an absolute constant c1 such that f(n,t,p) > c1·(n/t)· log(log t)/p. This improves on the known bounds \alpha \geq n/(t+1) and \alpha > 0.01(n/t) log t. The lasr inequality may be rewritten as f(n,t,3) > c·(n/t) log t, and suggests the study of the question f(n,t,p) = cp(n/t) log t.
Reviewer:  S.F.Kapoor
Classif.:  * 05C35 Extremal problems (graph theory)
05C99 Graph theory
60C05 Combinatorial probability
Keywords:  independent set; clique; random graphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag