Decomposition of complete uniform multi‐hypergraphs into Berge paths and cycles.

Abstract: In 2015, Bryant, Horsley, Maenhaut, and Smith, generalizing a well‐known conjecture by Alspach, obtained the necessary and sufficient conditions for the decomposition of the complete multigraph λ K n − I into cycles of arbitrary lengths, where <italic>I</italic> is empty, when λ ( n − 1 ) is even and <italic>I</italic> is a perfect matching, when λ ( n − 1 ) is odd. Moreover, Bryant in 2010, verifying a conjecture by Tarsi, proved that the obvious necessary conditions for packing pairwise edge‐disjoint paths of arbitrary lengths in λ K n are also sufficient. In this article, first, we obtain the necessary and sufficient conditions for packing edge‐disjoint cycles of arbitrary lengths in λ K n − I. Then, applying this result, we investigate the analogous problem of the decomposition of the complete uniform multihypergraph μ K n ( k ) into Berge cycles and paths of arbitrary given lengths. In particular, we show that for every integer μ ≥ 1, n ≥ 108 and 3 ≤ k < n, μ K n ( k ) can be decomposed into Berge cycles and paths of arbitrary lengths, provided that the obvious necessary conditions hold, thereby generalizing a result by Kühn and Osthus on the decomposition of K n ( k ) into Hamilton Berge cycles. [ABSTRACT FROM AUTHOR]