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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Cyclic partitions of complete and almost complete uniform hypergraphs
scientific article

    Statements

    Cyclic partitions of complete and almost complete uniform hypergraphs (English)
    0 references
    0 references
    1 July 2022
    0 references
    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)].
    0 references
    almost self-complementary hypergraph
    0 references
    uniform hypergraph
    0 references
    cyclically \(t\)-complementary hypergraph
    0 references
    \((t, k)\)-complementing permutation
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references