Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Maybe this question was already asked and forgive me if I can't formulate it well.

Lets assume we have a n-dimensional hypercube. If we want the smallest set of vertices such that the cube is inside the convex cone of the vertices we can take all the vertices on the main coordinates - (1,0,0,..,0),(0,1,0,..,0) etc.

My question is what is the maximum number of vertices we can take, such that 1. No vertex is in the interior of the convex cone generated by these edges. 2. The cube is not contained in the convex cone of the vertices.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

If you intend that the hypercube have a corner at the origin, and that the convex cone apex also be the origin, then for $n=3$, the cone that covers half the cube to one side of a diagonal plane seems to achieve the maximum:
           Cube Convex Cone
This cone includes 6 of the 8 vertices on its boundary (including the origin/apex in this count). The natural generalization of this construction to the $n$-cube includes (if I've counted correctly) $$2^{n-1} + 2^{n-2} = 3 \cdot 2^{n-2}$$ vertices.

But perhaps I am misunderstanding your question, for your second condition on the cone seems superfluous.

share|improve this answer
    
Yea, I believe your right. The reason I was looking for it is since I was looking at some kind of choosing from a worst case subset of the cube vertices that will allow receiving each of the vertices as an affine combination. Thank you! –  ifog Nov 23 '11 at 14:48

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.