Set systems with restricted \(t\)-wise intersections modulo prime powers
type: Item
instance of: scholarly article
title: Set systems with restricted \(t\)-wise intersections modulo prime powers
zbMATH Open document ID: 1228.05281
author: Rudy X. J. Liu
published in: The Electronic Journal of Combinatorics
publication date: 2009-07-08T00:00:00Z
full work available at URL: https://eudml.org/doc/117500
full work available at URL: v16i1n17.html
review text: Summary: 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 \({\mathcal L}=\{l_1,l_2,\ldots,l_s\}\) be a subset of \(\{0, 1, 2, \ldots, q-1\}\). If \({\mathcal F}\) is a family of subsets of an \(n\) element set \(X\) such that \(|F_{1}\cap \cdots \cap F_{t}| \pmod{q} \in {\mathcal L}\) for any collection of \(t\) distinct sets from \({\mathcal F}\) and \(|F| \pmod{q} \notin {\mathcal L}\) for every \(F\in {\mathcal F}\), then \[ |{\mathcal F}|\leq \frac{t(t-1)}{2}\sum_{i=0}^{2^{s-1}}\binom {n}{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.
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 5576417
zbMATH Keywords: non-prime-power composite moduli
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5576417