Geodesic
A Note on Packing of Uniform Hypergraphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1383-1388.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2022_42_4_a19,
     author = {Konarski, Jerzy and Wo\'zniak, Mariusz and \.Zak, Andrzej},
     title = {A {Note} on {Packing} of {Uniform} {Hypergraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1383--1388},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a19/}
}
TY  - JOUR
AU  - Konarski, Jerzy
AU  - Woźniak, Mariusz
AU  - Żak, Andrzej
TI  - A Note on Packing of Uniform Hypergraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1383
EP  - 1388
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a19/
LA  - en
ID  - DMGT_2022_42_4_a19
ER  - 
%0 Journal Article
%A Konarski, Jerzy
%A Woźniak, Mariusz
%A Żak, Andrzej
%T A Note on Packing of Uniform Hypergraphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1383-1388
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a19/
%G en
%F DMGT_2022_42_4_a19
Konarski, Jerzy; Woźniak, Mariusz; Żak, Andrzej. A Note on Packing of Uniform Hypergraphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1383-1388. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a19/

[1] B. Bollobás, Extremal Graph Theory (Academic Press, London-New York, 1978).

[2] B. Bollobás and S.E. Eldridge, Packing of graphs and applications to computational complexity, J. Combin. Theory Ser. B 25 (1978) 105–124. https://doi.org/10.1016/0095-8956(78)90030-8

[3] P. Keevash, The existence of designs (2014). arXiv:1401.3665

[4] A. Kostochka, C. Stocker and P. Hamburger, A hypergraph version of a graph packing theorem by Bollobás and Eldridge, J. Graph Theory 74 (2013) 222–235. https://doi.org/10.1002/jgt.21706

[5] P. Naroski, Packing of nonuniform hypergraphs—product and sum of sizes conditions, Discuss. Math. Graph Theory 29 (2009) 651–656. https://doi.org/10.7151/dmgt.1471

[6] O. Ore, The general Chinese reminder theorem, Amer. Math. Monthly 59 (1952) 365–370. https://doi.org/10.1080/00029890.1952.11988142

[7] M. Pilśniak and M. Woźniak, A note on packing of two copies of a hypergraph, Discuss. Math. Graph Theory 27 (2007) 45–49. https://doi.org/10.7151/dmgt.1343

[8] M. Pilśniak and M. Woźniak, On packing of two copies of a hypergraph, Discrete Math. Theor. Comput. Sci. 13 (2011) 67–74. https://doi.org/10.46298/dmtcs.537

[9] N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory Ser. B 25 (1978) 295–302. https://doi.org/10.1016/0095-8956(78)90005-9