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

2022/09/10 by Andrey Kupavskii, Kupavskii, Andrey, Fedor Noskov +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2209.04756

openalex publication_date 2022/09/10 · openalex created_date 2022/09/14 · openalex updated_date 2026/07/28

Abstract

Let \mathcal F₁, …, \mathcal F_ℓ be families of subsets of \1, …, n\. Suppose that for distinct k, k' and arbitrary F₁ ∈ \mathcal F_k, F₂ ∈ \mathcal F_k' we have |F₁ ∩ F₂|≤ m. What is the maximal value of |\mathcal F₁|… |\mathcal F_ℓ|? In this work we find the asymptotic of this product as n tends to infinity for constant ℓ and~m. This question is related to a conjecture of Bohn et al. that arose in the 2-level polytope theory and asked for the largest product of the number of facets and vertices in a two-level polytope. This conjecture was recently resolved by Weltge and the first author. The main result can be rephrased in terms of colorings. We give an asymptotic answer to the following question. Given an edge coloring of a complete m-uniform hypergraph into ℓ colors, what is the maximum of ∏ M_i, where M_i is the number of monochromatic cliques in i-th color?

Related

• Octopuses in the Boolean cube: families with pairwise small intersections, part II
• Two results about the hypercube
• The maximum sum of the sizes of all intersections within m-size families
• On the maximum number of points in a maximal intersecting family of finite sets
• Coloring hypergraphs that are the union of nearly disjoint cliques