Self-Complementary Hypergraphs

Abstract

In this thesis, we survey the current research into self-complementary hypergraphs, and present several new results. We characterize the cycle type of the permutations on n elements with order equal to a power of 2 which are k-complementing. The k-complementing permutations map the edges of a k-uniform hypergraph to the edges of its complement. This yields a test to determine whether a finite permutation is a k-complementing permutation, and an algorithm for generating all self-complementary k-uniform hypergraphs of order n, up to isomorphism, for feasible n. We also obtain an alternative description of the known necessary and sufficient conditions on the order of a self-complementary k-uniform hypergraph in terms of the binary representation of k. We examine the orders of t-subset-regular self-complementary uniform hyper- graphs. These form examples of large sets of two isomorphic t-designs. We restate the known necessary conditions on the order of these structures in terms of the binary representation of the rank k, and we construct 1-subset-regular self-complementary uniform hypergraphs to prove that these necessary conditions are sufficient for all ranks k in the case where t = 1. We construct vertex transitive self-complementary k-hypergraphs of order n for all integers n which satisfy the known necessary conditions due to Potocnik and Sajna, and consequently prove that these necessary conditions are also sufficient. We also generalize Potocnik and Sajna's necessary conditions on the order of a vertex transitive self-complementary uniform hypergraph for certain ranks k to give neces- sary conditions on the order of these structures when they are t-fold-transitive. In addition, we use Burnside's characterization of transitive groups of prime degree to determine the group of automorphisms and antimorphisms of certain vertex transitive self-complementary k-uniform hypergraphs of prime order, and we present an algorithm to generate all such hypergraphs. Finally, we examine the orders of self-complementary non-uniform hypergraphs, including the cases where these structures are t-subset-regular or t-fold-transitive. We find necessary conditions on the order of these structures, and we present constructions to show that in certain cases these necessary conditions are sufficient.