Citation:
Gosselin, Shonda. Self-Complementary Hypergraphs; Thesis Submitted to the Faculty of Graduate and Postdoctoral Studies in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Mathematics. Ottawa, 2009.
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.