Fix an integer Cut hypercube with an arbitrary -dimensional affine subspace of general position. *How many vertices has the obtained polyhedron*?

It occurs that grows polynomially, and not exponentially, with The goal of this post is to show the upper bound:

Consider first a usual cube in and cut it with a plane to obtain a polygon 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 which is a square – a 2-dimensional cube – and the plane . Also note that we have exactly 2 vertices belonging to the intersection of and namely, the ends of the corresponding segment. Since has facets, we can conclude that has not more than vertices. Finally, we can be slightly more accurate and remember that segments are connected, so we actually counted each vertex 2 times, so can have not more than vertices. Indeed, one can draw such a section.

Now we go back to the original problem. By a complete analogy,

Indeed, each vertex of the intersection lies in the intersection of some -facet and which is a -dimensional subspace, since we added one equation to the system of equations which describes Since has exactly such facets, we obtain 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.

### Like this:

Like Loading...

## About Dmitry Ostrovsky

PhD student with interests in learning theory, statistics, and optimization, working with Anatoli Juditsky and Zaid Harchaoui.

Я правильно понимаю, что нижняя граница (при ) равна ?

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

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