A Note on Packing of Uniform Hypergraphs

We say that two n-vertex hypergraphs H₁ and H₂ pack if they can be found as edge-disjoint subhypergraphs of the complete hypergraph K_n. 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 m_k(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 m_k(n) = Θ (n^k−1). In this note we show that this conjecture is far from being truth. Namely, we prove that the growth rate of m_k(n) is of order n^k/2 exactly for even k’s and asymptotically for odd k’s.