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

dmtcs:341 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, Vol. 6 no. 1 - https://doi.org/10.46298/dmtcs.341
A Note on Set Systems with no Union of Cardinality 0 modulo mArticle

Authors: Vince Grolmusz 1

  • 1 Department of Computer Science [Budapest]

\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.


Volume: Vol. 6 no. 1
Published on: January 1, 2003
Imported on: March 26, 2015
Keywords: hypergraphs,composite modulus,explicit constructions,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 340 times.
This article's PDF has been downloaded 406 times.