##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 774.05050

**Autor: ** Erdös, Paul; Hajnal, András; Simonovits, M.; Sós, V.T.; Szemerédi, E.

**Title: ** Turán-Ramsey theorems and simple asymptotically extremal structures. (In English)

**Source: ** Combinatorica 13, No.1, 31-56 (1993).

**Review: ** Let L_{1}, L_{2},...,L_{r} be given graphs (``forbidden'' graphs), and let n be a positive integer and f a given function; \alpha(G) denotes the maximum number of independent vertices in a graph G; RT(n,L_{1},L_{2},...,L_{r},f(n)) denotes the maximum number of edges in a graph G_{n} on n vertices, having \alpha(G_{n}) \leq f(n), whose edges may be coloured in r colours so that the subgraph of the ith colour contains no L_{i} (i = 1,2,...,r); the results of this paper generally apply to the case f(n) = o(n), and the maximum is usually denoted by RT(n,L_{1},L_{2},...,L_{r},o(n)). A sequence (S_{n}) of graphs for which \alpha(S_{n}) \leq f(n) and S_{n} has RT(n,L_{1},L_{2},...,L_{r},f(n))+o(n^{2}) edges, is asymptotically extremal for RT(n,L_{1},L_{2},...,L_{r},f(n)) if the edges of S_{n} may be r-coloured so that the subgraph of the ith colour contains no L_{i} (i = 1,...,r). In Theorem 2 a construction of *B. Bollobás* and *P. Erdös* [On a Ramsey-Turán type problem, J. Comb. Theory, Series B 21, 166-168 (1976; Zbl 337.05134)] used to prove that RT(n,K_{4},o(n)) \geq ^{1}/_{8} n^{2}-o(n^{2}) is generalized to prove the existence of a sequence of graphs that is asymptotically extremal for RT(n,K_{k1},K_{k2},...,K_{kr},o(n^{2})), where k_{1}, k_{2},...,k_{r} are integers each exceeding 2. Let \theta(L_{1},L_{2},...,L_{r}) denote the minimum real number such that RT(n,L_{1},L_{2},...,L_{r},f(n)) \leq \theta(L_{1},L_{2},...,L_{r})n^{2}+o(n^{2}); in Theorem 3 the values of \theta(K_{3},K_{3}), \theta(K_{3},K_{4}), \theta(K_{3},K_{5}), \theta(K_{4},K_{4}) are determined, as well as an asymptotically extremal sequence for each case; it is shown that the distance between two such sequences - - i.e. the minimum number of edge additions/deletions needed to transform one such sequence into another -- is o(n^{2}) in each case. Theorem 4: If p and q are odd integers, then RT(n,C_{p},C_{q},o(n)) = ^{1}/_{4} n^{2}+o(n^{2}).

The paper concludes with a list of open problems.

**Reviewer: ** W.G.Brown (Montreal)

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C55 Generalized Ramsey theory

05C38 Paths and cycles

**Keywords: ** Turán-Ramsey theorems; asymptotically extremal structures; colour; asymptotically extremal sequence

**Citations: ** Zbl 337.05134

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag