More results on Ramsey-Turán type problems (Q594896)

From MaRDI portal
Revision as of 19:04, 1 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
More results on Ramsey-Turán type problems
scientific article

    Statements

    More results on Ramsey-Turán type problems (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    1983
    0 references
    In [Combinat. Struct. Appl., Proc. Calgary Internat. Conf. Calgary 1969, 407-410 (1970; Zbl 0253.05145)] \textit{V.T.Sós} raised a general scheme of new problems that can be considered as common generalizations of the problems treated in the classical results of Ramsey and Turán. This paper is a continuation of a sequence of papers on this subject. One of the main results is the following: Given \(k\geq 2\) and \(\varepsilon> 0\), let \(G_n\) be a sequence of graphs of order \(n\) size at least \((1/2)\left(\frac{3k-5}{3k-2}+\varepsilon\right)n^2\) edges such that the cardinality of the largest independent set in \(G_n\) is \(o(n)\). Let \(H\) be any graph of arboricity at most \(k\). Then there exists an \(n_0\) such that all \(G_n\) with \(n> n_0\) contain a copy of \(H\). This result is best possible in the case \(H=K_{2k}\).
    0 references
    arboricity
    0 references
    sequence of graphs
    0 references
    largest independent set
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references