Discrete Mathematics & Theoretical Computer Science, Vol 15, No 2 (2013)

Font Size:  Small  Medium  Large

Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs

Shonda Gosselin, Artur Szymanski, Adam Pawel Wojda


A {\em cyclic $q$-partition} of a hypergraph $(V,E)$ is a partition of the edge set $E$ of the form $\{F,F^\theta,F^{\theta^2}, \ldots, F^{\theta^{q-1}}\}$ for some permutation $\theta$ of the vertex set $V$. Let $V_n = \{ 1,2,\ldots,n\}$. For a positive integer $k$, $V_n\choose k$ denotes the set of all $k$-subsets of $V_n$. For a nonempty subset $K$ of $V_{n-1}$, we let $\mathcal{K}_n^{(K)}$ denote the hypergraph $\left(V_n, \bigcup_{k\in K} {V_n\choose k}\right)$. In this paper, we find a necessary and sufficient condition on $n, q$ and $k$ for the existence of a cyclic $q$-partition of $\mathcal{K}_n^{(V_{k})}$. In particular, we prove that if $p$ is prime then there is a cyclic $p^{\alpha}$-partition of $\mathcal{K}^{(V_k)}_n$ if and only if $p^{\alpha + \beta}$ divides $n$, where $\beta = \lfloor \log_p k\rfloor$. As an application of this result, we obtain two sufficient conditions on $n_1,n_2,\ldots,n_t, k$, $\alpha$ and a prime $p$ for the existence of a cyclic $p^\alpha$-partition of the complete $t$-partite $k$-uniform hypergraph $\mathcal K^{(k)}_{n_1,n_2,\ldots,n_t}$.

Full Text: PDF PostScript