zbMATH — the first resource for mathematics

On Ramsey - Turan type theorems for hypergraphs. (English) Zbl 0511.05049
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.
Reviewer: L.Zaremba

05C65 Hypergraphs
05C35 Extremal problems in graph theory
05C55 Generalized Ramsey theory
Full Text: DOI
[1] B. Bollobás andP. Erdos, On a Ramsey–Turán type problem,J. Comb. Th. Ser. B 21 (1976) 166–168. · Zbl 0337.05134 · doi:10.1016/0095-8956(76)90057-5
[2] P. Erdos, A. Hajnal, V. T. Sós andE. Szemerédi, More results on Ramsey–Turán type problems,Combinatorica,3 (1) (1983).
[3] P. Erdos andA. Hajnal, On chromatic number of graphs and set systems,Acta Math. Acad. Sci. Hungar. 17 (1966) 61–99. · Zbl 0151.33701 · doi:10.1007/BF02020444
[4] P. Erdos, On extremal problems of graphs and generalized graphs,Israel J. Math. 2 (1964) 183–190. · Zbl 0129.39905 · doi:10.1007/BF02759942
[5] P. Erdos andV. T. Sós, Some remarks on Ramsey’s and Turán’s theorem.Comb. Theory and Appl. (P. Erdos et al. eds.)Math. Coll. Soc. J. Bolyai 4 Balatonfüred (1969) 395–404.
[6] P. Erdos andM. H. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc. 52 (1946) 1087–1091. · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7
[7] V. T. Sós, On extremal problems in graph theoryProc. Calgary Internat. Conf. on Comb. Structures (1969) 407–410.
[8] E. Szemerédi, On graphs containing no complete subgraph with 4 vertices (in Hungarian),Mat. Lapok 23 (1972) 111–116.
[9] P. Turán. Eine Extremalaufgabe aus der Graphentheorie (in Hungarian),Mat. Fiz. Lapok 48 (1941) 436–452.see also: On the theory of graphs,Colloquium Math. 3 (1954), 19–30.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.