A Note on Set Systems with no Union of Cardinality 0 modulo m

Abstract : \emphAlon, Kleitman, Lipton, Meshulam, Rabin and \emphSpencer (Graphs. Combin. 7 (1991), no. 2, 97-99) proved, that for any hypergraph \textbf\textitF=\F_1,F_2,\ldots, F_d(q-1)+1\, where q is a prime-power, and d denotes the maximal degree of the hypergraph, there exists an \textbf\textitF_0⊂ \textbf\textitF, such that |\bigcup_F∈\textbf\textitF_0F| ≡ 0 (q). We give a direct, alternative proof for this theorem, and we also show that an explicit construction exists for a hypergraph of degree d and size Ω (d^2) which does not contain a non-empty sub-hypergraph with a union of size 0 modulo 6, consequently, the theorem does not generalize for non-prime-power moduli.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.41-44
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00958986
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:58:30
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:08:31

Fichier

dm060103.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958986, version 1

Collections

Citation

Vince Grolmusz. A Note on Set Systems with no Union of Cardinality 0 modulo m. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.41-44. 〈hal-00958986〉

Partager

Métriques

Consultations de la notice

62

Téléchargements de fichiers

253