Abstract
The paper deals with common generalizations of classical results of Ramsey and Turán. The following is one of the main results. Assumek≧2, ε>0,G n is a sequence of graphs ofn-vertices and at least 1/2((3k−5) / (3k−2)+ε)n 2 edges, and the size of the largest independent set inG n iso(n). LetH be any graph of arboricity at mostk. Then there exists ann 0 such that allG n withn>n 0 contain a copy ofH. This result is best possible in caseH=K 2k .
Similar content being viewed by others
References
B. Bollobás andP. Erdős, On a Ramsey—Turán type problem.J. C. T. (B) 21 (1976), 166–168.
W. Brown andM. Simonovits, Preprint.
P. Erdős, Graph Theory and Probability,Canadian J. Math. Journal of Mathematics 11 (1959), 34–38.
P. Erdős andVera T. Sós, Some remarks on Ramsey’s and Turán’s theorem.Coll. Math. Soc. J. Bolyai,4.Comb. Theory and its Appl., North-Holland (1969), 395–404.
P. Erdős andVera T. Sós, Problems and results on Ramsey—Turán type theorems,Proc. West Coast Conf. on Combinatorics, Graph Th. and Computing, Humboldt State Univ. Arcata (1979), 17–23.
P. Erdős andVera T. Sós, Problems and results on Ramsey—Turán type theorems II,Studia Sci. Math. Hung. 14 (1979), 27–36.
P. Erdoős andA. H. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc. 52 (1946), 1087–1091.
J. Gillis, Note on a property of measurable sets,J. London Math. Soc. 11 (1936), 139–141.
Vera T. Sós, On extremal problems in graph theory,Comb. structures and their appl. Proc. Calgary International Conference, Calgary (1969), 407–410.
E. Szemerédi, Graphs without complete quadrilaterals (in Hungarian),Mat. Lapok 23 (1973), 113–116.
E. Szemerédi, On sets containing nok elements in arithmetic progression,Acta Arithmetica 27 (1975), 199–245.
E. Szemerédi, Regular partitions of graphs,Coll. internat. C. N. R. S. 260 Probl. Combin. et Th. Graphes (1978), 399–402.
A. A. Zykov, On some properties of linear complexes (in Russian),Mat. Sbornik, N. S. 24 (1949), 163–188, andAmer. Math. Soc. Trans. 79 (1952).