2020/08/17 by Andrey Kupavskii, Stefan Weltge, Kupavskii, Andrey +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2008.07153
10 pages
arxiv created 2020/08/17 · arxiv updated 2020/08/18
Let A,B ⊆ ℝd both span ℝd such that ⟨ a, b ⟩ ∈ \0,1\ holds for all a ∈ A, b ∈ B. We show that |A| ⋅ |B| ≤ (d+1) 2d . This allows us to settle a conjecture by Bohn, Faenza, Fiorini, Fisikopoulos, Macchia, and Pashkovich (2015) concerning 2-level polytopes. Such polytopes have the property that for every facet-defining hyperplane H there is a parallel hyperplane H' such that H ∪ H' contain all vertices. The authors conjectured that for every d-dimensional 2-level polytope P the product of the number of vertices of P and the number of facets of P is at most d 2d+1, which we show to be true.