A Note on Packing of Uniform Hypergraphs
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 hy...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2437 |
| _version_ | 1797725529318621184 |
|---|---|
| author | Konarski Jerzy Woźniak Mariusz Żak Andrzej |
| author_facet | Konarski Jerzy Woźniak Mariusz Żak Andrzej |
| author_sort | Konarski Jerzy |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T10:32:34Z |
| format | Article |
| id | doaj.art-42c7d9977e034e758cbf371a3c6e150d |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T10:32:34Z |
| publishDate | 2022-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-42c7d9977e034e758cbf371a3c6e150d2023-09-02T09:07:26ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-11-014241383138810.7151/dmgt.2437A Note on Packing of Uniform HypergraphsKonarski Jerzy0Woźniak Mariusz1Żak Andrzej2AGH University of Science and TechnologyAGH University of Science and TechnologyAGH University of Science and TechnologyWe 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.https://doi.org/10.7151/dmgt.2437packinghypergraphs05c35 |
| spellingShingle | Konarski Jerzy Woźniak Mariusz Żak Andrzej A Note on Packing of Uniform Hypergraphs Discussiones Mathematicae Graph Theory packing hypergraphs 05c35 |
| title | A Note on Packing of Uniform Hypergraphs |
| title_full | A Note on Packing of Uniform Hypergraphs |
| title_fullStr | A Note on Packing of Uniform Hypergraphs |
| title_full_unstemmed | A Note on Packing of Uniform Hypergraphs |
| title_short | A Note on Packing of Uniform Hypergraphs |
| title_sort | note on packing of uniform hypergraphs |
| topic | packing hypergraphs 05c35 |
| url | https://doi.org/10.7151/dmgt.2437 |
| work_keys_str_mv | AT konarskijerzy anoteonpackingofuniformhypergraphs AT wozniakmariusz anoteonpackingofuniformhypergraphs AT zakandrzej anoteonpackingofuniformhypergraphs AT konarskijerzy noteonpackingofuniformhypergraphs AT wozniakmariusz noteonpackingofuniformhypergraphs AT zakandrzej noteonpackingofuniformhypergraphs |