Set systems with restricted t-wise intersections modulo prime powers
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.
- Set systems with restricted intersections modulo prime powers
- On set systems with restricted intersections modulo p and p-ary t-designs
- On set systems with restricted k-wise L-intersection modulo a prime, and beyond
- scientific article; zbMATH DE number 1088263
- Improved bounds on families under \(k\)-wise set-intersection constraints
- On set systems with restricted intersections modulo p and p-ary t-designs
- A strengthened inequality of Alon-Babai-Suzuki's conjecture on set systems with restricted intersections modulo \(p\)
- scientific article; zbMATH DE number 1088263 (Why is no real title available?)
- On set systems with restricted k-wise L-intersection modulo a prime, and beyond
- Set systems with restricted intersections modulo prime powers
- Set systems with k-wise L-intersections and codes with restricted Hamming distances
This page was built for publication: Set systems with restricted \(t\)-wise intersections modulo prime powers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028811)
