DIMACS TR: 2000-11

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

Author: Vince Grolmusz


Alon, Kleitman, Lipton, Meshulam, Rabin and Spencer (Graphs. Combin. 7 (1991), no. 2, 97-99) proved, that for any hypergraph ${\cal F}=\{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 ${\cal F}_0\subset {\cal F}$, such that $|\bigcup_{F\in{\cal F}_0}F|\equiv 0\pmod{q}$. We give a direct, alternative proof for this theorem, and we also give an explicit construction of a hypergraph of degree $d$ and size $\Omega(d^2)$ which does not contain a non-empty sub-hypergraph with a union of size 0 modulo 6.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-11.ps.gz
DIMACS Home Page