Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 818.05037
Autor: Erdös, Paul; Rödl, Vojtech
Title: Coverings of r-graphs by complete r-partite subgraphs. (In English)
Source: Random Struct. Algorithms 6, No.2-3, 319-322 (1995).
Review: A relationship between the following two extremal problems is established: Let G be an r-uniform hypergraph and f(G) be the minimum number of complete r-partite graphs necessary to cover all edges of G. Set f(r, n) = max f(G), where the maximum runs over all r-uniform hypergraphs on n vertices. On the other hand, denote by T(r, s, n), r < s < n, the Turán number. The authors show that, for any r > 2, f(r+1, n) = (1- o(1)) T(r, r+1, n).
Reviewer: P.Horák (Bratislava)
Classif.: * 05C35 Extremal problems (graph theory)
05C65 Hypergraphs
Keywords: extremal problems; hypergraph; cover; Turán number
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag