Some remarks on Ramsey’s and Turán’s theorem. (English) Zbl 0209.28002
Combinat. Theory Appl., Colloq. Math. Soc. János Bolyai 4, 395-404 (1970).
[For the entire collection see Zbl 0205.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,l)\) is the largest integer for which there is a graph of \(n\) vertices and \(f(n;k,l)\) edges which contains no complete subgraph of \(k\) vertices and no independent set of \(l\) vertices. Trivially \(f(n;3,l) \leq {1 \over 2}nl\). The authors prove that if \(l = o(n)\) then \(f(n;2r+1,l) = {1 \over 2}(1-1/r)n^2(1+o(1))\). The most striking unsolved problem states: Let \(l=o(n)\). Is it true that \(f(n;4,l) = o(n^2)\)? Szemerédi recently showed that for \(l=o(n)\), \(f(n;4,l)<(1+o(1))n^2/8\). Several other related results are proved and there are many unsolved problems.
The authors prove several theorems which they call of the Ramsey-Turán type, and also several unsolved problems are posed. \(f(n;k,l)\) is the largest integer for which there is a graph of \(n\) vertices and \(f(n;k,l)\) edges which contains no complete subgraph of \(k\) vertices and no independent set of \(l\) vertices. Trivially \(f(n;3,l) \leq {1 \over 2}nl\). The authors prove that if \(l = o(n)\) then \(f(n;2r+1,l) = {1 \over 2}(1-1/r)n^2(1+o(1))\). The most striking unsolved problem states: Let \(l=o(n)\). Is it true that \(f(n;4,l) = o(n^2)\)? Szemerédi recently showed that for \(l=o(n)\), \(f(n;4,l)<(1+o(1))n^2/8\). Several other related results are proved and there are many unsolved problems.
Reviewer: Paul Erdős
MSC:
| 05C55 | Generalized Ramsey theory |
