Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)

enter image description here

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?

share|improve this question
    
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. –  Andrew Salmon 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. –  Milo Chen 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$. –  Andrew Salmon Jun 6 '13 at 9:03
    
Ahh yup - overlooked the obvious - thanks –  Milo Chen Jun 6 '13 at 9:03
1  
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}$? –  Peter KoŇ°inár Jun 6 '13 at 9:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.