Let H = (V, E) be an r-uniform hypergraph and let ℱ ⊂ 2 V. A matching M of H is (α, ℱ)-perfect if for each ℱ ∈ ℱ, at least α F| vertices of F are covered by M. Our main result is a theorem giving sufficient conditions for an r-uniform hypergraph to have a (1 - ε, ℱ-perfect matching. As a special case of our theorem we obtain the following result. Let K(n, r) denote the complete r-uniform hypergraph with n vertices. Let t and r be fixed positive integers where t ≥ r ≥ 2. Then, K (n, r) can be packed with edge-disjoint copies of K(t, r) such that each vertex is incident with only o(nr-1) unpacked edges. This extends a result of Rödl .
|Original language||English (US)|
|Number of pages||8|
|Journal||Graphs and Combinatorics|
|State||Published - Dec 2005|
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics