# How many cuts does it take to remove any $n$ vertices from an $m$-dimensional hypercube?

For instance, in $m=3$ dimensions (cube), the following $n=3$ corners (red) can be cut off with a minimum of $C=2$ planes (blue). (Note you are only allowed to cut off the vertices in red.)

So what about the general case of $n$ vertices on an $m$-dimensional hypercube? What is the minimum number of cuts $C(m,n)$ required to cut off any $n$ given vertices?

• Even on a square, the answer depends on which vertices you select--whether they are adjacent or not. Take two corners of a square sharing a common edge vs. two corners of a square with no edge between them.
– A.S
Jun 6 '13 at 8:56
• @andewsalmon - I'm interested in the minimum number to cut off any $n$ given vertices, meaning I allow for the case of not being adjacent. Sure, for adjacent cases you may use less cuts, but I need to be able to cut off any $n$ given vertices in $C(m,n)$ cuts. Jun 6 '13 at 9:00
• The example of the square is a counterexample to the conjecture you proposed. Notice that $2$ cuts are needed, which is greater than $m-1 = 1$.
– A.S
Jun 6 '13 at 9:03
• Ahh yup - overlooked the obvious - thanks Jun 6 '13 at 9:03
• A generalization of the opposite-corners-in-square: Colour the vertices of the $m$-dimensional hypercube with two colours so that two adjacent vertices are always coloured differently. If you take any $n$-member set of vertices of the same colours, my intuition suggests you'll need all $n$ cuts (i.e. every vertex will need its own cut) opposite-corners case. Of course, if you take more than half of the vertices, you will be able to reduce the number of cuts. Maybe the number of cuts required would be $\min{n,2^n-m}$? Jun 6 '13 at 9:18

Peter Košinár’s conjecture from his comment is true for $n\le 2^{m-1}$. To see this note that each hyperplane cutting off more than one cube vertex is cutting off two adjacent vertices. But the case $n>2^{m-1}$ is more complicated. Nevertheless, the upper bound $C(m,n)\le 2^{m}-n$ can be easily proved by induction by $m$.