Binary scalar products

Abstract

Let $A,B\subseteq {\mathbb{R}}^d$ both span ${\mathbb{R}}^d$ such that $⟨a,b⟩\in \{0,1\}$ holds for all $a\in A$, $b\in B$. We show that $|A|\cdot |B|\le (d+1)2^d$. 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^{\prime }$ such that $H\cup H^{\prime }$ 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{2}^{d+1}$, which we show to be true.

10 pages