## Cutting hypercube by an affine subspace

Fix an integer $k.$  Cut hypercube $C_n = [0,1]^n \subset \mathbb{R}^n$  with an arbitrary $k$-dimensional affine subspace $S_k \subset \mathbb{R}^n$  of general position.  How many vertices $V_k(n)$  has the obtained polyhedron?

It occurs that $V_k(n)$  grows polynomially, and not exponentially, with $n.$  The goal of this post is to show the upper bound: $\displaystyle V_k(n) \le n^k.$

Consider first a usual cube $C_3$  in $R^3,$  and cut it with a plane $S_2$  to obtain a polygon $P.$ How many vertices can this polygon have? The answer is, of course, 6.

Let us prove this obvious fact. First note that all vertices lie in the intersection of some facet of $C_3,$  which is a square – a  2-dimensional cube – and the plane $S_2$. Also note that we have exactly 2 vertices belonging to the intersection of $F$  and $S_2,$  namely, the ends of the corresponding segment. Since $C_3$  has $2 * 3 = 6$  facets, we can conclude that $P$  has not more than $2 * 6 = 12$  vertices. Finally, we can be slightly more accurate and remember that segments are connected, so we actually counted each vertex 2 times, so $P$  can have not more than $12/2 = 6$  vertices. Indeed, one can draw such a section.

Now we go back to the original problem. By a complete analogy, $\displaystyle V_k(n) \le n V_{k-1}(n-1).$

Indeed, each vertex of the intersection lies in the intersection of some $(n-1)$-facet and $S_k,$  which is a $k$-dimensional subspace, since we added one equation to the system of equations which describes $S_k.$  Since $C_n$  has exactly $2n$  such facets, we obtain $\displaystyle V_k(n) \le 2n V_{k-1}(n-1).$  Finally, each vertex lies in the intersection of two facets, so we can divide the right-hand side by 2, and “wind off” the recurrence to obtain the claimed upper bound. PhD student with interests in statistics, optimization, and machine learning.
This entry was posted in Pretty little things and tagged . Bookmark the permalink.

### 3 Responses to Cutting hypercube by an affine subspace

1. Артур says:

Я правильно понимаю, что нижняя граница (при $k \le n$) равна $k \cdot 2^{k-1}$ ?

• ostrodmit says:

Хз! А зависящую от n слабо придумать? Что будет, если угол отсекать? А если по главной диагонали проводить?

• ostrodmit says:

Anyway, here’s an article about that. It seems that an expected number of vertices is polynomial in log(n)
http://arxiv.org/pdf/math/9812123.pdf