Erdős, Pál and Hajnal, András and Simonovits, Miklós and T. Sós, Vera and Szemerédi, Endre (1993) TuránRamsey theorems and simple asymptotically extremal structures. COMBINATORICA, 13 (1). pp. 3156. ISSN 02099683

Text
Erdos1993_Article_TuranRamseyTheoremsAndSimpleA.pdf Download (1MB)  Preview 
Abstract
This paper is a continuation of [10], where P. Erdos, A. Hajnal, V. T. Sos. and E. Szemeredi investigated the following problem: Assume that a so called forbidden graph L and a function f(n) = o(n) are fixed. What is the maximum number of edges a graph G(n) on n vertices can have without containing L as a subgraph, and also without having more than f(n) independent vertices? This problem is motivated by the classical Turan and Ramsey theorems, and also by some applications of the Turin theorem to geometry, analysis (in particular, potential theory) [27 29], [1113]. In this paper we are primarily interested in the following problem. Let (G(n)) be a graph sequence where G(n) has n vertices and the edges of G(n) are coloured by the colours chi1,...,chi(r), so that the subgraph of colour chi(nu) contains no complete subgraph K(pnu), (nu = 1,...,r). Further, assume that the size of any independent set in G(n) is o(n) (as n > infinity). What is the maximum number of edges in G(n) under these conditions? One of the main results of this paper is the description of a procedure yielding relatively simple sequences of asymptotically extremal graphs for the problem. In a continuation of this paper we shall investigate the problem where instead of alpha(G(n)) = o(n) we assume the stronger condition that the maximum size of a K(p)free induced subgraph of G(n) is o(n).
Item Type:  Article 

Uncontrolled Keywords:  AMS subject classification code (1991): 05C35, 05C55; 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  27 Jun 2020 06:47 
Last Modified:  27 Jun 2020 06:47 
URI:  http://real.mtak.hu/id/eprint/110601 
Actions (login required)
Edit Item 