Perfect matching and Hamilton cycle decomposition of complete balanced (k+1)-partite k-uniform hypergraphs

Abstract Let K k + 1 , n ( k ) denote the complete balanced ( k + 1 ) -partite k-uniform hypergraph, whose vertex set consists of k + 1 parts, each has n vertices and whose edge set contains all the k-element subsets with no two vertices from one part. In this paper, we prove that if k∣n and ( n k , k ) = 1 , then K k + 1 , n ( k ) has a perfect matching decomposition; if ( n , k ) = 1 , then K k + 1 , n ( k ) has a Hamilton tight cycle decomposition. In both cases, we use constructive methods which imply that we also give a polynomial algorithm to find a perfect matching decomposition or a Hamilton tight cycle decomposition.