Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  511.05049
Autor:  Erdös, Paul; Sós, Vera T.
Title:  On Ramsey - Turan type theorems for hypergraphs. (In English)
Source:  Combinatorica 2, 289-295 (1982).
Review:  Let Hr be an r-uniform hypergraph and f(n; Hr) be the minimal integer so that any r-uniform hypergraph on n vertices and more than f(n; Hr) edges contains a subgraph isomorphic to Hr. The extimation of f(n; Hr) 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; Hr,\ell) be the smallest integer for which every graph of n vertices and more than f(n; Hr,\ell) edges either contains a subgraph isomorphic to Hr or it contains an independent set of size \ell. Let, moreover, E = {h1,...,hm} be the edge-set of Hr such that, for every i, 1 \leq i \leq m, there exists a j\ne i with |hi\cap hj| \geq 2. If limn ––> oo\binom{n}{r}-1f(n; Hr) = c(Hr) and lim\epsilon ––> 0limn ––> oo\binom{n}{r}-1f(n; Hr,\epsilon n) = c^*(H) then c^*(Hr) = c(Hr). There are also given conditions ensuring c^*(Hr) = 0. The authors state also 10 open problems; a few of them concern graphs of uniform edge density.
Reviewer:  L.Zaremba
Classif.:  * 05C65 Hypergraphs
                   05C35 Extremal problems (graph theory)
                   05C55 Generalized Ramsey theory
Keywords:  r-uniform hypergraph; edge density; spanned subgraph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page