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

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