go-v.orgdoi

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

Xiaojie Liu · The Electronic Journal of Combinatorics · 2009

  • DOI 10.37236/255
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2009

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2009

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.

Open the resolved locator · 10.37236/255

Metadata licence: OpenAlex metadata (CC0)