How many vertices can a hypercube-hyperplane intersection have?

876 Views Asked by At

Consider the n-hypercube $[-1, 1]^n$, and intersect it with an n-hyperplane. The intersection is in general an $(n-1)$-dimensional polytope. How many vertices can it have?

For example, when $n=2$, it must be a line segment, so it can have at most 2 vertices. When $n=3$, it can have at most 6 vertices. I'm having difficulty with $n\ge 4$.

When $n=4$, we can intersect the cube by $\{x | \sum_{i=1}^4 x_i = 0\}$ to get a rhombic dodecahedron with 14 vertices, so that's a lower bound at least. rhombic dodecahedron

2

There are 2 best solutions below

0
On BEST ANSWER

Just a few ideas without complete proof:

Let us consider the hypercube $[\color{red}{-1},1]^n$ and intersect it with a hyperplane $\{x\in\mathbb{R}^n \; | \; v^Tx=c\},\;v\in\mathbb{R}^n,\;c\in\mathbb{R}.$ The vertices of the intersection are the points on the plane that have $n-1$ coordinates with an absolute value of $1$ and one coordinate with an absolute value of at most $1.$

The cases $n=2$ and $n=3$ indicate that the "best" hyperplane can be obtained by using $v=(1,\ldots,1)^T$ and $c=0.$ I have not managed to prove this, yet. But if we assume it, we can easily find formulae for the number of vertices of the intersection.

If $n$ is even, then we have to construct the vertex $x$ by using $\frac{n}{2}$ times the value $1$ and $\frac{n}{2}$ times the value $-1.$ Therefore, there are $$n\choose{\frac{n}{2}}$$ vertices.

If $n$ is odd, then we have to construct the vertex $x$ by using $\frac{n-1}{2}$ times the value $1,$ $\frac{n-1}{2}$ times the value $-1$ and once the value $0.$ Therefore, there are $$n \cdot {n-1\choose{\frac{n-1}{2}}}$$ vertices.

Edit:

For even $n$, we can do better. Let $v=(1,\ldots,1,0),\;c=0.$ Then we can fill the first $n-1$ coordinates of $x$ with $\frac{n-2}{2}$ times the value $1$, $\frac{n-2}{2}$ times the value $-1$ and one $0.$ The last coordinate of $x$ is either $-1$ or $1.$ This results in $$ 2(n-1){n-2\choose \frac{n-2}{2}} $$ vertices.

0
On

Consider the hyperplane $x_1 = 1$. The intersection has $2^{n-1}$ vertexes, isn't it ? So the maximum number in the general case is at least that!