On Ramsey - Turan type theorems for hypergraphs
type: Item
instance of: scholarly article
title: On Ramsey - Turan type theorems for hypergraphs
zbMATH Open document ID: 0511.05049
DOI: 10.1007/BF02579235
author: Vera T. Sós
author: P. Erdős
published in: Combinatorica
publication date: 1982-01-01T00:00:00Z
review text: Let \(H^r\) be an r-uniform hypergraph and \(f(n;H^r)\) be the minimal integer so that any \(r\)-uniform hypergraph on \(n\) vertices and more than \(f(n;H^r)\) edges contains a subgraph isomorphic to \(H^r\). The extimation of \(f(n;H^r)\) is the fundamental problem of extremal graph theory. The paper deals with extremal theory for hypergraphs. The main result is that the situation is quite different for hypergraphs. To be more precisely, let \(f(n;H^r,\ell)\) be the smallest integer for which every graph of \(n\) vertices and more than \(f(n;H^r,\ell)\) edges either contains a subgraph isomorphic to \(H^r\) or it contains an independent set of size \(\ell\). Let, moreover, \(E=\{h_1,\dots,h_m\}\) be the edge-set of \(H^r\) such that, for every \(i\), \(1\leq i\leq m\), there exists a \(j\neq i\) with \(|h_i\cap h_j|\geq 2\). If \(\lim_{n\to\infty}\binom{n}{r}^{-1}f(n;H^r)=c(H^r)\) and \(\lim_{\varepsilon\to 0}\lim_{n\to\infty}\binom{n}{r}^{-1}f(n;H^r,\varepsilon n)=c^*(H)\) then \(c^*(H^r)=c(H^r)\). There are also given conditions ensuring \(c^*(H^r)=0\). The authors state also 10 open problems; a few of them concern graphs of uniform edge density.
reviewed by: Leszek S. Zaremba
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 3805596
zbMATH Keywords: r-uniform hypergraph
zbMATH Keywords: edge density
zbMATH Keywords: spanned subgraph
MaRDI profile type: Publication
cites work: On a Ramsey-Turán type problem
cites work: On chromatic number of graphs and set-systems
cites work: On extremal problems of graphs and generalized graphs
cites work: On the structure of linear graphs
full work available at URL: https://doi.org/10.1007/bf02579235
OpenAlex ID: W1972261509
Recommended article: Some Ramsey-Turán type results for hypergraphs
Recommended article: On the Ramsey-Turán numbers of graphs and hypergraphs
Recommended article: Q3912619
Recommended article: A generalization of a Ramsey‐type theorem on hypermatchings
Recommended article: Q4105701
Recommended article: Q4100121
Recommended article: On the Size‐Ramsey Number of Hypergraphs
Recommended article: Q3204500
Recommended article: On a Ramsey-Turán type problem
Recommended article: Q4293771
description: scientific article; zbMATH DE number 3805596