1
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Small doubling, atomic structure and $$\ell$$-divisible set families

Preprint
, ,

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### 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^{\Omega(n\log \ell/\ell)}$$. On the other hand, if the intersection of {\em 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'.

### Author and article information

###### Journal
30 March 2021
###### Article
2103.16479
e54678d2-5fb7-42d9-96a8-631960d2971b