Abstract
Let F0 be a fixed k-uniform hypergraph. The problem of finding the integer F0-packing number νF0 (H) of a k-uniform hypergraph H is an NP-hard problem. Finding the fractional F0-packing number νF0* (H) however can be done in polynomial time. In this paper we give a lower bound for the integer F0-packing number νF0 (H) in terms of νF0* (H) and show that νF0 (H) ≥ νF0* (H) - o (| V (H) |k).
Original language | English |
---|---|
Pages (from-to) | 245-268 |
Number of pages | 24 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 97 |
Issue number | 2 |
DOIs | |
State | Published - Mar 2007 |
Keywords
- Hypergraph regularity lemma
- Packings