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