Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  766.05060
Autor:  Erdös, Paul; Füredi, Zoltán; Tuza, Zsolt
Title:  Saturated r-uniform hypergraphs. (In English)
Source:  Discrete Math. 98, No.2, 95-104 (1991).
Review:  The following dual version of Turán's problem is considered: for a given r-uniform hypergraph F, determine the minimum number of edges in an r-uniform hypergraph H on n vertices, such that F\not\subset H but a subhypergraph isomorphic to F occurs whenever a new edge (r- tuple) is added to H. For some types of F we find the exact value of the minimum or describe its asymptotic behavior as n tends to infinity; namely, for Hr(r+1,r), Hr(2r-2,2) and Hr(r+1,3), where Hr(p,q) denotes the family of all r-uniform hypergraphs with p vertices and q edges. Several problems remain open.
Classif.:  * 05C65 Hypergraphs
                   05C35 Extremal problems (graph theory)
Keywords:  Turán's problem; minimum number; hypergraphs

© 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