Cyclically t-complementary uniform hypergraphs

Abstract

A cyclically t-complementary k-hypergraph is a k-uniform hypergraph with vertex set V and edge set E for which there exists a permutation 2 Sym.V/ such that the sets E; E ; E 2; : : : ; E t􀀀1 partition the set of all k-subsets of V. Such a permutation is called a .t; k/-complementing permutation. The cyclically t-complementary k-hypergraphs are a natural and useful generalization of the self-complementary graphs, which have been studied extensively in the past due to their important connection to the graph isomorphism problem. For a prime p, we characterize the cycle type of the .pr ; k/- complementing permutations 2 Sym.V/ which have order a power of p. This yields a test for determining whether a permutation in Sym.V/ is a .pr ; k/-complementing permutation, and an algorithm for generating all of the cyclically pr-complementing k- hypergraphs of order n, for feasible n, up to isomorphism. We also obtain some necessary and sufficient conditions on the order of these structures. This generalizes previous results due to Ringel, Sachs, Adamus, Orchel, Szymański, Wojda, Zwonek, and Bernaldez.