2023/09/19 by Andrey Kupavskii, Kupavskii, Andrey, Fedor Noskov +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Approximation and Integration #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.2309.10921
openalex publication_date 2023/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 d2d - 1? Recently, Kupavskii and Weltge~\citeKupavskii2020 settled this question in positive. A key element in their proof is a more general result for families of vectors in ℝ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 F1, …, F_ℓ be families of subsets of \1, …, n\. We suppose that for distinct k, k' and arbitrary F1 ∈ Fk, F2 ∈ Fk' we have |F1 ∩ F2|\leqslant m. We are interested in the maximal value of |F1|… |F_ℓ| and the structure of the extremal example. In the previous paper on the topic, the authors found the asymptotics of this product for constant ℓ 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.