##
**Zentralblatt MATH**

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

**Zbl.No: ** 209.28002

**Autor: ** Erdös, Paul; Sós, V.T.

**Title: ** Some remarks on Ramsey's and Turán's theorem (In English)

**Source: ** Combinat. Theory Appl., Colloquia Math. Soc. János Bolyai 4, 395-404 (1970).

**Review: ** [For the entire collection see Zbl 205.00201.]

The authors prove several theorems which they call of the Ramsey-Turán type, and also several unsolved problems are posed. f(n; k,\ell) is the largest integer for which there is a graph of n vertices and f(n; k,\ell) edges which contains no complete subgraph of k vertices and no independent set of \ell vertices. Trivially f(n; 3,\ell) \leq ^{1}/_{2} n \ell. The authors prove that if \ell = o(n) then f(n; 2r+1,\ell) = ^{1}/_{2} (1-1/r)n^{2}(1+o(1)). The most striking unsolved problem states: Let \ell = o(n). Is it true that f(n; 4,\ell) = o(n^{2})? Szemerédi recently showed that for \ell = o(n), f(n; 4,\ell) < (1+o(1))n^{2}/8. Several other related results are proved and there are many unsolved problems.

**Classif.: ** * 05C55 Generalized Ramsey theory

**Citations: ** Zbl 205.00201(EA)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag