Cyclic partitions of complete uniform hypergraphs

Artur Szymański ; A. Paweł Wojda

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

By $K^{(k)}_n$ we denote the complete $k$-uniform hypergraph of order $n$, $1\le k \le n-1$, i.e. the hypergraph with the set $V_n=\{ 1,2,...,n\}$ of vertices and the set $V_n \choose k$ of edges. If there exists a permutation $\sigma$ of the set $V_n$ such that $\{ E,\sigma (E),..., \sigma^{q-1}(E) \}$ is a partition of the set $V_n \choose k$ then we call it cyclic $q$-partition of $K^{(k)}_n$ and $\sigma$ is said to be a $(q,k)$-complementing. In the paper, for arbitrary integers $k,q$ and $n$, we give a necessary and sufficient condition for a permutation to be $(q,k)$-complementing permutation of $K^{(k)}_n$. By $\tilde{K}_n$ we denote the hypergraph with the set of vertices $V_n$ and the set of edges $2^{V_n} - \{ \emptyset , V_n \}$. If there is a permutation $\sigma$ of $V_n$ and a set $E \subset 2^{V_n} - \{ \emptyset , V_n \}$ such that $\{ E, \sigma (E),..., \sigma^{p-1}(E) \}$ is a $p$-partition of $ 2^{V_n} - \{ \emptyset , V_n \}$ then we call it a cyclic $p$-partition of $K_n$ and we say that $\sigma$ is $p$-complementing. We prove that $\tilde{K}_n$ has a cyclic $p$-partition if and only if $p$ is prime and $n$ is a power of $p$ (and $n > p$). Moreover, any $p$-complementing permutation is cyclic.

Détail

DOI : 10.37236/390

Classification : 05C65
Mots-clés : complete uniform hypergraph, cyclic partition, complementing permutation