Turán-Ramsey theorems and simple asymptotically extremal structures
type: Item
instance of: scholarly article
title: Turán-Ramsey theorems and simple asymptotically extremal structures
zbMATH Open document ID: 0774.05050
DOI: 10.1007/BF01202788
author: Vera T. Sós
author: Andras Hajnal
author: Miklós Simonovits
author: P. Erdős
author: Endre Szemerédi
published in: Combinatorica
publication date: 1993-08-16T00:00:00Z
review text: Let \(L_1,\) \(L_2,\dots,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\); \(\text{RT}(n,L_1,L_2,\dots,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 \(i\)th colour contains no \(L_i\) \((i=1,2,\dots,r)\); the results of this paper generally apply to the case \(f(n)=o(n)\), and the maximum is usually denoted by \(\text{RT}(n,L_1,L_2,\dots,L_r,o(n))\). A sequence \((S_n)\) of graphs for which \(\alpha(S_n)\leq f(n)\) and \(S_n\) has \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))+o(n^2)\) edges, is asymptotically extremal for \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))\) if the edges of \(S_n\) may be \(r\)-coloured so that the subgraph of the \(i\)th colour contains no \(L_i\) \((i=1,\dots,r)\). In Theorem 2\ a construction of \textit{B. Bollobás} and \textit{P. Erdős} [On a Ramsey-Turán type problem, J. Comb. Theory, Series B 21, 166-168 (1976; Zbl 0337.05134)] used to prove that \(\text{RT}(n,K_4,o(n))\geq{1\over 8}n^2-o(n^2)\) is generalized to prove the existence of a sequence of graphs that is asymptotically extremal for \(\text{RT}(n,K_{k_1},K_{k_2},\dots,K_{k_r},o(n^2))\), where \(k_1\), \(k_2,\dots,k_r\) are integers each exceeding 2. Let \(\vartheta(L_1,L_2,\dots,L_r)\) denote the minimum real number such that \(\text{RT}(n,L_1,L_2,\dots,L_r,f(n))\leq\vartheta(L_1,L_2,\dots,L_r)n^2+o(n^2)\); in Theorem 3 the values of \(\vartheta(K_3,K_3)\), \(\vartheta(K_3,K_4)\), \(\vartheta(K_3,K_5)\), \(\vartheta(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: …
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 247011
zbMATH Keywords: Turán-Ramsey theorems
zbMATH Keywords: asymptotically extremal structures
zbMATH Keywords: colour
zbMATH Keywords: asymptotically extremal sequence
reviewed by: William G. Brown
MaRDI profile type: Publication
Wikidata QID: Q101119739
cites work: On a Ramsey-Turán type problem
cites work: Extremal problems for directed graphs
cites work: Algorithmic Solution of Extremal Digraph Problems
cites work: More results on Ramsey-Turán type problems
cites work: On some applications of graph theory. I
cites work: On Some Applications of Graph Theory III
cites work: The Construction of Certain Graphs
cites work: On the structure of linear graphs
cites work: Some Ramsey-Turán type results for hypergraphs
cites work: Maxima for Graphs and a New Proof of a Theorem of Turán
cites work: On the theory of graphs
cites work: Q3214957
cites work: Q4774297
full work available at URL: https://doi.org/10.1007/bf01202788
OpenAlex ID: W2068922840
description: scientific article