Let $H$ be the $n$dimensional hypercube, i.e. $\{0,1\}^n$ with edges between two vertices if and only if they differ in exactly one coordinate. We say that an edge is in direction $i$ if its endpoints differ in exactly the $i$'th coordinate. Suppose $V$ is a subset of $H$ such that $V > 2^{n1}$. Is it true that at least one connected component of the graph induced by $V$ contains edges in all $n$ direction?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Yes, this is true. Thanks to Sukhada Fadnavis and Seva for pointing out in the comments that the argument I had written here was wrong. Instead I will point you to the paper where this is proved
As far as I can tell from looking at the literature, it is not known if there are configurations of more than $2^{n1}$ vertices for which one can not find $n+1$ of them which induce a tree with an edge in every direction. This would be a strengthening of the result in question. 

