<p>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 <a href="http://books.google.com/books?id=-jtadMIhPGoC&amp;lpg=PA26&amp;ots=HdfFTJGz8y&amp;dq=size%20of%20coefficients%200-1%20polytope&amp;pg=PA29#v=onepage&amp;q&amp;f=false" rel="nofollow">here</a>.</p>

<p>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. </p>

<p>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 <a href="http://www.sciencedirect.com/science/article/pii/S0097316597927801" rel="nofollow">Alon and Vu</a></p>

CC BY-SA 3.0
2013-06-30T23:11:57.683Z
2013-07-01T04:34:44.480Z
2013-07-01T04:34:44.480Z
Sasho Nikolov
<p>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$. </p>

CC BY-SA 3.0
2013-06-30T20:29:30.023Z
2013-06-30T20:29:30.023Z
Peter Shor 
<p>$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. </p>

<p>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?</p>

CC BY-SA 3.0
2013-06-30T17:54:40.733Z
Can you please make your question more precise/correct. There are several mistakes, e.g., you gave the definition for affine hull (not convex hull). There are also several issues with dimension.
Austin Buchanan
<convex-optimization><integer-programming><convex-geometry>
On facets of 01-polytope
echuly
# On facets of 01-polytope

(Asked by: username_0 on 2013-06-30)

$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?

**Tags:** convex-optimization, integer-programming, convex-geometry

> **Comments:**
> **username_1**: Can you please make your question more precise/correct. There are several mistakes, e.g., you gave the definition for affine hull (not convex hull). There are also several issues with dimension.  

---

## 2 answers

### Answer by username_2 on 2013-06-30. Score: 7

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](http://books.google.com/books?id=-jtadMIhPGoC&lpg=PA26&ots=HdfFTJGz8y&dq=size%20of%20coefficients%200-1%20polytope&pg=PA29#v=onepage&q&f=false).

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](http://www.sciencedirect.com/science/article/pii/S0097316597927801)


---

### Answer by username_3 on 2013-06-30. Score: 5

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$.


---

