Abstract | ||
---|---|---|
A theorem of Lovasz asserts that (H)=(H) r=2 for every r-partitehypergraph H (where and denote the covering number and fractional coveringnumber respectively). Here it is shown that the same upper bound is valid for amore general class of hypergraphs: those which admit a partition (V 1 ; : : : ; V k ) of thevertex set and a partition p 1 + + p k of r such that je \ V i j p i r=2 for everyedge e and every 1 i k. Moreover, strict inequality holds when r > 2, ... |
Year | Venue | Keywords |
---|---|---|
1996 | Combinatorica | upper bound |
DocType | Volume | Issue |
Journal | 16 | 2 |
Citations | PageRank | References |
3 | 0.70 | 1 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ron Aharoni | 1 | 380 | 66.56 |
Ron Holzman | 2 | 287 | 43.78 |
michael krivelevich | 3 | 1688 | 179.90 |