Kneser's theorem for codes and $\ell$-divisible set families
Preprint
Abstract
A $k$-wise $\ell$-divisible set family is a collection $\mathcal{F}$ of subsets of ${ \{1,\ldots,n \} }$ such that any intersection of $k$ sets in $\mathcal{F}$ has cardinality divisible by $\ell$. If $k=\ell=2$, it is well-known that $|\mathcal{F}|\leq 2^{\lfloor n/2 \rfloor}$. We generalise this by proving that $|\mathcal{F}|\leq 2^{\lfloor n/p\rfloor}$ if $k=\ell=p$, for any prime number $p$. For arbitrary values of $\ell$, we prove that $4\ell^2$-wise $\ell$-divisible set families $\mathcal{F}$ satisfy $|\mathcal{F}|\leq 2^{\lfloor n/\ell\rfloor}$ and that the only families achieving the upper bound are atomic, meaning that they consist of all the unions of disjoint subsets of size $\ell$. This improves upon a recent result by Gishboliner, Sudakov and Timon, that arrived at the same conclusion for $k$-wise $\ell$-divisible families, with values of $k$ that behave exponentially in $\ell$. Our techniques rely heavily upon a coding-theory analogue of Kneser's Theorem from additive combinatorics.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Two Remarks on Eventown and Oddtown ProblemsSIAM Journal on Discrete Mathematics, 2018
- Additive combinatorics methods in associative algebrasConfluentes Mathematici, 2017
- Critical Pairs for the Product Singleton BoundIEEE Transactions on Information Theory, 2015
- On Subsets with Cardinalities of Intersections Divisible by a Fixed IntegerEuropean Journal of Combinatorics, 1983
- On the ranks of some (0, 1)-matrices with constant row sumsJournal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics, 1981
- Boolean designs and self-dual matroidsLinear Algebra and its Applications, 1975
- On Subsets with Intersections of Even CardinalityCanadian Mathematical Bulletin, 1969
- Absch tzung der asymptotischen Dichte von SummenmengenMathematische Zeitschrift, 1953