Article in volume
Authors:
Mariusz Woźniak
Department of Applied MathematicsAGH University of Science and Technologyal. Mickiewicza 3030-059 KrakówPOLAND
email: mwozniak@agh.edu.pl
Andrzej Żak
Faculty of Appied MathematicsAGH University of Science and Technologyal. Mickliewicza 3030-059 KrakówPOLAND
email: zakandrz@agh.edu.pl
Title:
A note on packing of uniform hypergraphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1383-1388
Received: 2021-06-24 , Revised: 2021-11-02 , Accepted: 2021-11-02 , Available online: 2021-11-12 , https://doi.org/10.7151/dmgt.2437
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\geq 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.
Keywords:
packing, hypergraphs
References:
- B. Bollobás, Extremal Graph Theory (Academic Press, London-New York, 1978).
- 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 - P. Keevash, The existence of designs (2014).
arXiv: 1401.3665 - 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 - P. Naroski, Packing of nonuniform hypergraphs - product and sum of sizes conditions, Discuss. Math. Graph Theory 29(3) (2009) 651–656.
https://doi.org/10.7151/dmgt.1471 - O. Ore, The general Chinese Reminder Theorem, Amer. Math. Monthly 59 (1952) 365–370.
https://doi.org/10.1080/00029890.1952.11988142 - 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 - 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 - 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
Close