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