Introduction - University of the Ryukyus.pdfVIP

INTEGER AND FRACTIONAL PACKINGS OF HYPERGRAPHS ¨ V. RODL, M. SCHACHT, M. H. SIGGERS, AND N. TOKUSHIGE Abstract. Let F0 be a fixed k-uniform hypergraph. The problem of finding the integer F -packing number ν (H) of a k-uniform hypergraph H is an 0 F0 NP-hard problem. Finding the fractional F -packing number ν ∗ (H) however 0 F0 can be done in polynomial time. In this paper we give a lower bound for the integer F -packing number ν (H) in terms of ν ∗ (H) and show that 0 F0 F0 νF0 (H) ≥ ν ∗ (H) − o(|V (H)|k ). F0 1. Introduction For positive integer , we denote by [] the set {1, . . . , }. For set V and integer k ≥ 1, we denote by V the set of all k-element subsets of V . By y = x ± ε we k mean |y − x | ε. A subset H ⊂ V (H) is called a k-uniform hypergraph on k vertex set V (H). Notice that we are identifying a hypergraph H with its edges, so |H| will be the number of edges in the hypergraph. For U ⊂ V (H), we denote by H [U] the subhypergraph of H induced by U (i.e. H [U] = H ∩ U). k For fixed hypergraphs F0 and H, a subhypergraph F ⊂ H is a copy of F0 if there exists a bijection of the vertex sets : V (F ) → V (F ) ⊂ V (H) such that 0 { (u ), . . . , (u )} is an edge in F if a