On facets of 01-polytope

Question

$0,1$-polytopse are fundamental objects in combinatorial geometry and comvex optimization. I am interested in the size of binary representation of hyperplanes to use in the framework of computational complexity theory.

Let $v_1, v_2, \dots, v_N$ be points in $\{0,1\} \subseteq \mathbb{R}^n$. Does every facet of the convex hull of these points lie on a supporting hyperplane $$\sum_{i=1}^n a_i x_i = t,$$ where every coefficient $a_i$ is either 0 or 1? If not, how many bits are needed to express the coefficients $a_i$ of a facet hyperplane?

Answer 1

For your second question, the number of bits is $O(n^2 \log n)$ (i.e. $O(n\log n)$ per coefficient) and there are examples where it is $\Omega(n^2\log n)$, i.e. the bound is tight. See Corollary 26 here.

The ideas are standard, and anyone who has seen an analysis of the ellipsoid algorithm will be familiar with this. Say you have a facet in the hyperplane spanned by vertices $v_1, \ldots v_{n-1}$. If the hyperplane is through the origin, it is defined by $a^T x = 0$ for the vector $a$ satisfying $V^Ta = 0$ where $V$ is the matrix containing $v_1, \ldots, v_{n-1}$ as columns. Using the fact that $V$ is a 0-1 matrix, you can bound the coefficients of $a$ using Cramer's rule and the Hadamard bound. If the hyperplane is not through the origin the argument is the same but the defining equality is $a^T x = 1$ and the system of equalities you need to solve is $V^Ta = e$ where $e$ is the all-ones vector.

The lower bound is based on observing that everything above is tight and constructing a matrix $V$ such that removing any row from $V$ gives a matrix with a huge determinant. This construction is the one thing about your question which is research level, see the book or this paper by Alon and Vu

Answer 2

Consider the plane through the points $(1,0,0,0)$, $(0,1,0,0)$, $(0,0,1,0)$, $(1,1,1,1)$. If you add the origin to this set of points, the hyperplane is a facet of the convex hull. The equation is $x_1 + x_2 + x_3 - 2x_4 = 1$. The coefficient on $x_4$ is not $0$ or $\pm 1$.