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

arXiv2103.16479MaRDI QIDQ6364136FDOQ6364136

Lior Gishboliner, István Tomon, Benny Sudakov

Publication date: 30 March 2021

Abstract: Let $mathcalFsubset{2}^{[n]}$ be a set family such that the intersection of any two members of $mathcalF$ has size divisible by $ell$. The famous Eventown theorem states that if $ell=2$ then $|mathcalF|leq{2}^{lfloorn/2floor}$, 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^{lfloorn/ellfloor}$. Yet, as was shown by Frankl and Odlyzko, these families are far from maximal. For infinitely many $ell$, they constructed families $mathcalF$ as above of size $2^{Omega(nlogell/ell)}$. On the other hand, if the intersection of any number of sets in $mathcalFsubset{2}^{[n]}$ has size divisible by $ell$, then it is easy to show that $|mathcalF|leq{2}^{lfloorn/ellfloor}$. In 1983 Frankl and Odlyzko conjectured that $|mathcalF|leq{2}^{(1+o(1))n/ell}$ holds already if one only requires that for some $k=k(ell)$ any $k$ distinct members of $mathcalF$ have an intersection of size divisible by $ell$. We completely resolve this old conjecture in a strong form, showing that $|mathcalF|leq{2}^{lfloorn/ellfloor}+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'.

This page was built for publication: Small doubling, atomic structure and $\ell$-divisible set families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6364136)