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 L1, L2,...,Lr 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,L1,L2,...,Lr,f(n)) denotes the maximum number of edges in a graph Gn on n vertices, having \alpha(Gn) \leq f(n), whose edges may be coloured in r colours so that the subgraph of the ith colour contains no Li (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,L1,L2,...,Lr,o(n)). A sequence (Sn) of graphs for which \alpha(Sn) \leq f(n) and Sn has RT(n,L1,L2,...,Lr,f(n))+o(n2) edges, is asymptotically extremal for RT(n,L1,L2,...,Lr,f(n)) if the edges of Sn may be r-coloured so that the subgraph of the ith colour contains no Li (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,K4,o(n)) \geq 1/8 n2-o(n2) is generalized to prove the existence of a sequence of graphs that is asymptotically extremal for RT(n,Kk1,Kk2,...,Kkr,o(n2)), where k1, k2,...,kr are integers each exceeding 2. Let \theta(L1,L2,...,Lr) denote the minimum real number such that RT(n,L1,L2,...,Lr,f(n)) \leq \theta(L1,L2,...,Lr)n2+o(n2); in Theorem 3 the values of \theta(K3,K3), \theta(K3,K4), \theta(K3,K5), \theta(K4,K4) 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(n2) in each case. Theorem 4: If p and q are odd integers, then RT(n,Cp,Cq,o(n)) = 1/4 n2+o(n2).
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