Discrete Mathematics & Theoretical Computer Science, Vol 6, No 1 (2003)

Font Size:  Small  Medium  Large

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

Vince Grolmusz


Alon, Kleitman, Lipton, Meshulam, Rabin and Spencer (Graphs. Combin. 7 (1991), no. 2, 97-99) proved, that for any hypergraph F={F1,F2,…, Fd(q-1)+1}, where q is a prime-power, and d denotes the maximal degree of the hypergraph, there exists an F0⊂ F, such that |⋃F∈F0F| ≡ 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 Ω(d2) 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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page