Cyclic Partitions of Complete and Almost Complete Uniform Hypergraphs

Abstract

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=∏i≥0(kini)s = \prod {_{i \ge 0}\left( {_{{k_i}}^{{n_i}}} \right)} , and ni and ki are the entries in the base-pα representations of n and k, respectively. This existence result yields a combinatorial argument which generalizes Lucas’ classic 1878 number theory result to prime powers, which was originally proved by Davis and Webb in 1990 by another method. In addition, we prove an alternative statement of the necessary and sufficient conditions for the existence of a pα-complementary k-hypergraph, and the equivalence of these two conditions yield an interesting relationship between the base-p representation and the base-pα representation of a positive integer n. Finally, we determine a set of necessary and sufficient conditions on n for the existence of a t-complementary k-uniform hypergraph on n vertices for composite values of t, extending previous results due to Wojda, Szymański and Gosselin.

Keywords

• almost self-complementary hypergraph
• uniform hypergraph
• cyclically t-complementary hypergraph
• (t,k)-complementing permutation
• 05c65
• 05e20
• 05c25
• 05c85