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

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