Hypercube vertex sampling with largest convex cone - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T11:16:32Z http://mathoverflow.net/feeds/question/81693 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/81693/hypercube-vertex-sampling-with-largest-convex-cone Hypercube vertex sampling with largest convex cone ifog 2011-11-23T09:02:30Z 2011-11-23T13:11:52Z <p>Maybe this question was already asked and forgive me if I can't formulate it well.</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/81693/hypercube-vertex-sampling-with-largest-convex-cone/81704#81704 Answer by Joseph O'Rourke for Hypercube vertex sampling with largest convex cone Joseph O'Rourke 2011-11-23T13:11:52Z 2011-11-23T13:11:52Z <p>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: <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/CubeCone.jpg" alt="Cube Convex Cone"><br /> 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.</p> <p>But perhaps I am misunderstanding your question, for your second condition on the cone seems superfluous.</p>