1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

A Note on Packing of Uniform Hypergraphs

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1383 - 1388
Received: 24 Jun 2021
Accepted: 02 Nov 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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

MSC 2010

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

[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 Search in Google Scholar

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

[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 Search in Google Scholar

[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 Search in Google Scholar

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

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo