Small doubling, atomic structure and $\ell$-divisible set families
OPEN ACCESS
Loading...
Author / Producer
Date
2022-09-30
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Let $\mathcal{F}\subset 2^{[n]}$ be a set family such that the intersection of any two members of $\mathcal{F}$ has size divisible by $\ell$. The famous Eventown theorem states that if $\ell=2$ then $|\mathcal{F}|\leq 2^{\lfloor n/2\rfloor}$, and this bound can be achieved by, e.g., an `atomic' construction, i.e. splitting the ground set into disjoint pairs and taking their arbitrary unions. Similarly, splitting the ground set into disjoint sets of size $\ell$ gives a family with pairwise intersections divisible by $\ell$ and size $2^{\lfloor n/\ell\rfloor}$. Yet, as was shown by Frankl and Odlyzko, these families are far from maximal. For infinitely many $\ell$, they constructed families $\mathcal{F}$ as above of size $2^{Ω(n\log \ell/\ell)}$. On the other hand, if the intersection of any number of sets in $\mathcal{F}\subset 2^{[n]}$ has size divisible by $\ell$, then it is easy to show that $|\mathcal{F}|\leq 2^{\lfloor n/\ell\rfloor}$. In 1983 Frankl and Odlyzko conjectured that $|\mathcal{F}|\leq 2^{(1+o(1)) n/\ell}$ holds already if one only requires that for some $k=k(\ell)$ any $k$ distinct members of $\mathcal{F}$ have an intersection of size divisible by $\ell$. We completely resolve this old conjecture in a strong form, showing that $|\mathcal{F}|\leq 2^{\lfloor n/\ell\rfloor}+O(1)$ if $k$ is chosen appropriately, and the $O(1)$ error term is not needed if (and only if) $\ell \, | \, n$, and $n$ is sufficiently large. Moreover the only extremal configurations have `atomic' structure as above. Our main tool, which might be of independent interest, is a structure theorem for set systems with small 'doubling'.
Permanent link
Publication status
published
Editor
Book title
Journal / series
Volume
11
Pages / Article No.
38586
Publisher
Alliance of Diamond Open Access Journals
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Eventown; l-divisible set family; Frankl-Odlyzko conjecture
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
02500 - Forschungsinstitut für Mathematik / Institute for Mathematical Research
Notes
Funding
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)