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)n2(1+o(1)). The most striking unsolved problem states: Let \ell = o(n). Is it true that f(n; 4,\ell) = o(n2)? Szemerédi recently showed that for \ell = o(n), f(n; 4,\ell) < (1+o(1))n2/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