Generating self-complementary uniform hypergraphs

Abstract

In 2007, Szymanski and Wojda proved that for positive integers n; k with k<n, a self-complementary k-uniform hypergraph of order n exists if and only if n/k is even. In this paper, we characterize the cycle type of a k-complementing permutation in Sym.n/ which has order equal to a power of 2. This yields a test for determining whether a finite permutation is a k-complementing permutation, and an algorithm for generating all self-complementary k-hypergraphs of order n, up to isomorphism, for feasible n.We also obtain an alternative description of the necessary and sufficient conditions on the order of a self-complementary k-uniform hypergraph, in terms of the binary representation of k. This extends previous results for the cases k D 2; 3; 4 due to Ringel, Sachs, Suprunenko, Kocay and Szymanski.