Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2504.19304 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916709505433600 |
|---|---|
| author | Lin, Chenying Zémor, Gilles |
| author_facet | Lin, Chenying Zémor, Gilles |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19304 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Kneser's theorem for codes and $\ell$-divisible set families Lin, Chenying Zémor, Gilles Combinatorics 05D05 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. |
| title | Kneser's theorem for codes and $\ell$-divisible set families |
| topic | Combinatorics 05D05 |
| url | https://arxiv.org/abs/2504.19304 |