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
      , ,

      Read this article at

      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'.

          Related collections

          Author and article information

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

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          Custom metadata
          math.CO

          Combinatorics
          Combinatorics

          Comments

          Comment on this article