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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page