Cyclic partitions of complete and almost complete uniform hypergraphs (Q2151208)

A \(k\)-uniform hypergraph on a vertex set \(V\) and an edge set \(E\) is said to be \(s\)-almost \(t\)-complementary of order \(n\) if \(|V| = n\) and there exists a permutation \(\theta\) of \(V\) such that the sets \(E, E^\theta,\dots, E^{\theta^{t-1}}\) are all disjoint and together they cover all but \(s\) of the \(k\)-sets of \(V\). This concept generalises concepts which have been studied in particular instances in previous works. For example, when \(s=0\) these are known as complementary \(k\)-graphs [\textit{S. Gosselin}, Eur. J. Comb. 31, No. 7, 1629--1636 (2010; Zbl 1219.05106)], and for \(s=1\) and \(t=2\) they are known as almost self-complementary \(k\)-graphs [\textit{A. P. Wojda}, Discuss. Math., Graph Theory 38, No. 2, 607--610 (2018; Zbl 1404.05144)]. The main result of the paper finds a sufficient condition for the existence of \(s\)-almost \(t\)-complementary \(k\)-graphs in the case where \(t\) is a prime power. More precisely, for \(k < n\), \(p\) prime, if \(n = \sum_{i \geq 0} n_i p^{\alpha i}\) and \(k = \sum_{i \geq 0} k_i p^{\alpha i}\) are the base-\(p^\alpha\) representations of \(n\) and \(k\), then there exists an \(s\)-almost \(p^{\alpha}\)-complementary \(k\)-graph of order \(n\), for \(s = \prod_{i \geq 0} \binom{n_i}{k_i}\). The second main result is similar in spirit and concerns composite values of \(t\). A number of previously-known results on \(s\)-almost \(t\)-complementary \(k\)-graphs and prime congruences are deduced as corollaries from these main results. As an example, the authors give a combinatorial proof of the generalisation of Lucas' theorem for prime powers [\textit{K. S. Davis} and \textit{W. A. Webb}, Eur. J. Comb. 11, No. 3, 229--233 (1990; Zbl 0704.11002)].