Abstract | ||
---|---|---|
We say that two n-vertex hypergraphs H-1 and H-2 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) = Theta (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. |
Year | DOI | Venue |
---|---|---|
2022 | 10.7151/dmgt.2437 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | DocType | Volume |
packing, hypergraphs | Journal | 42 |
Issue | ISSN | Citations |
4 | 1234-3099 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jerzy Konarski | 1 | 0 | 0.34 |
Mariusz Wozniak | 2 | 0 | 0.68 |
Andrzej Zak | 3 | 0 | 0.34 |