Set Systems with Restricted $t$-wise Intersections Modulo Prime Powers

  • Rudy X. J. Liu

Abstract

We give a polynomial upper bound on the size of set systems with restricted $t$-wise intersections modulo prime powers. Let $t\geq 2$. Let $p$ be a prime and $q=p^{\alpha}$ be a prime power. Let ${\cal L}=\{l_1,l_2,\ldots,l_s\}$ be a subset of $\{0, 1, 2, \ldots, q-1\}$. If ${\cal F}$ is a family of subsets of an $n$ element set $X$ such that $|F_{1}\cap \cdots \cap F_{t}| \pmod{q} \in {\cal L}$ for any collection of $t$ distinct sets from ${\cal F}$ and $|F| \pmod{q} \notin {\cal L}$ for every $F\in {\cal F}$, then $$ |{\cal F}|\leq {t(t-1)\over2}\sum_{i=0}^{2^{s-1}}{n\choose i}. $$ Our result extends a theorem of Babai, Frankl, Kutin, and Štefankovič, who studied the $2$-wise case for prime power moduli, and also complements a result of Grolmusz that no polynomial upper bound holds for non-prime-power composite moduli.

Published
2009-06-05
Article Number
N17