Prairie Mathematics Colloquium: Shonda Dueck

We consider cyclic partitions of the complete k-uniform hypergraph on a finite set V , minus a set of s edges, s ≥ 0. An s-almost t-complementary k-hypergraph is a k-uniform hypergraph with vertex set V and edge set E for which there exists a permutation θ ∈ Sym(V ) such that the sets E, Eθ, Eθ2 , . . . , Eθt−1 partition the set of all k-subsets of V minus a set of s edges. Such a permutation θ is called an s-almost (t,k)-complementing permutation. The s-almost t-complementary k-hypergraphs are a natural generalization of the almost self-complementary graphs which were previously studied by Clapham, Kamble et al, and Wojda. We prove the existence of an s-almost p-complementary k-hypergraph of order n, where p is prime, s = Q ni
, and ni and ki i≥0 ki are the entries in the base-p representations of n and k, respectively. This existence result yields a combinatorial proof of Lucas’ classic 1878 theorem. We also present a construction for vertex- transitive q-complementary uniform hypergraphs, for any prime power q, which can be viewed as a generalization of the Paley graph construction to uniform hypergraphs.