Saturated r-uniform hypergraphs

✍ Scribed by Paul Erdős; Zoltán Füredi; Zsolt Tuza

• Book ID: 103056873
• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 708 KB
• Volume: 98
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(91)90035-z

✦ Synopsis

ErdGs, P., Z. Fiiredi and Z. Tuza, Saturated r-uniform hypergraphs, Discrete Mathematics 98 (1991) 95-104.

The following dual version of Turin'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 + 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 H,(r + 1, r), H,(2r -2, 2) and H,(r + 1, 3), where H,@, q) denotes the family of all r-uniform hypergraphs with p vertices and q edges. Several problems remain open.