Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs

Abstract : A cyclic q-partition of a hypergraph (V,E) is a partition of the edge set E of the form $\F,F^θ,F^θ², \ldots, F^θ^q-1\$ for some permutation θ of the vertex set V. Let Vₙ = \ 1,2,\ldots,n\. For a positive integer k, Vₙ\choose k denotes the set of all k-subsets of Vₙ. For a nonempty subset K of V_n-1, we let \mathcalKₙ^(K) denote the hypergraph ≤ft(Vₙ, \bigcup_k∈ K Vₙ\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 \mathcalKₙ^(V_k). In particular, we prove that if p is prime then there is a cyclic p^α-partition of \mathcalK^(Vₖ)ₙ if and only if p^α + β divides n, where β = \lfloor \logₚ k\rfloor. As an application of this result, we obtain two sufficient conditions on n₁,n₂,\ldots,n_t, k, α and a prime p for the existence of a cyclic p^α-partition of the complete t-partite k-uniform hypergraph \mathcal K^(k)_n₁,n₂,\ldots,n_t.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.215--222
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00980768
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 18 avril 2014 - 16:43:55
Dernière modification le : jeudi 16 août 2018 - 17:00:02
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:34:19

Fichier

1779-8284-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00980768, version 1

Collections

Citation

Shonda Gosselin, Andrzej Szymański, Adam Pawel Wojda. Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.215--222. 〈hal-00980768〉

Partager

Métriques

Consultations de la notice

695

Téléchargements de fichiers

258