Octopuses in the Boolean cube: families with pairwise small intersections, part II

Abstract

The problem we consider originally arises from 2-level polytope theory. This class of polytopes generalizes a number of other polytope families. One of the important questions in this filed can be formulated as follows: is it true for a $d$-dimensional 2-level polytope that the product of the number of its vertices and the number of its $d-1$ dimensional facets is bounded by $d{2}^{d-1}$? Recently, Kupavskii and Weltge~\cite{Kupavskii2020} settled this question in positive. A key element in their proof is a more general result for families of vectors in ${\mathbb{R}}^d$ such that the scalar product between any two vectors from different families is either $0$ or $1$. Peter Frankl noted that, when restricted to the Boolean cube, the solution boils down to an elegant application of the Harris--Kleitman correlation inequality. Meanwhile, this problem becomes much more sophisticated when we consider several families. Let ${\mathcal{F}}_1,\dots ,{\mathcal{F}}_{\ell }$ be families of subsets of $\{1,\dots ,n\}$. We suppose that for distinct $k,k^{\prime }$ and arbitrary $F_1\in {\mathcal{F}}_k,F_2\in {\mathcal{F}}_{k^{\prime }}$ we have $|F_1\cap F_2|⩽m.$ We are interested in the maximal value of $|{\mathcal{F}}_1|\dots |{\mathcal{F}}_{\ell }|$ and the structure of the extremal example. In the previous paper on the topic, the authors found the asymptotics of this product for constant $\ell$ and $m$ as $n$ tends to infinity. However, the possible structure of the families from the extremal example turned out to be very complicated. In this paper, we obtain a strong structural result for the extremal families.