A Note on Packing of Uniform Hypergraphs

Abstract

We say that two n-vertex hypergraphs H1 and H2 pack if they can be found as edge-disjoint subhypergraphs of the complete hypergraph Kn. Whilst the problem of packing of graphs (i.e., 2-uniform hypergraphs) has been studied extensively since seventies, much less is known about packing of k-uniform hypergraphs for k ≥ 3. Naroski [Packing of nonuniform hypergraphs - product and sum of sizes conditions, Discuss. Math. Graph Theory 29 (2009) 651–656] defined the parameter mk(n) to be the smallest number m such that there exist two n-vertex k-uniform hypergraphs with total number of edges equal to m which do not pack, and conjectured that mk(n) = Θ (nk−1). In this note we show that this conjecture is far from being truth. Namely, we prove that the growth rate of mk(n) is of order nk/2 exactly for even k’s and asymptotically for odd k’s.

Keywords

• packing
• hypergraphs
• 05c35