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.

Advertisements

About Dmitry Ostrovsky

PhD student with interests in learning theory, statistics, and optimization, working with Anatoli Juditsky and Zaid Harchaoui.
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} ?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s