Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 487.05054
Autor: Erdös, Paul; Sos, Vera T.
Title: On Turan-Ramsey type theorems. II. (In English)
Source: Stud. Sci. Math. Hung. 14, 27-36 (1979).
Review: This paper is a continuation of: P.Erdös, V.T.Sós [Comb. Theory Appl., Colloq. Math. Soc. János Bolyai 4, 395-404 (1970; Zbl 209.28002)], V.T.Sós [Conf. Comb. Struct. Appl., Calgary 1969, 407-410 (1970; Zbl 253.05145)]. Let f(n; K1,...,kr) be the largest integer for which there is an r-coloring of the edges of a complete graph Kn (the graph of the ith colored edges will be denoted by Gi) satisfying Kki\not\subseteq Gi(1 \leq i \leq r) and sumi = 1r-1 e(Gi) = f(n; k1,...,kr)). The determination of the function f is considured in this paper. In particular, the following result is proved. Theorem. There are constants c1 > 0 and c2 > 0 such that \frac{n2}{4}+c1\epsilon n2 < f(n; 3,3,\epsilon n) < \frac{n2}{4}+c2\epsilon n2, where the first inequality depends upon n > n0(\epsilon). Applications of this reasoning leads to improvement on bounds for classical Ramsey numbers, for example, they prove r(3,3,n) = \sigma(n3) or more generally r(3,3,...,3,n) = \sigma(nr+1).
Reviewer: R.Faudres
Classif.: * 05C55 Generalized Ramsey theory
05C35 Extremal problems (graph theory)
Keywords: Ramsey numbers; extremal graphs
Citations: Zbl.209.280; Zbl.253.05145
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag