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?

1$\begingroup$ Is it known how many connected components there can be for such a subgraph? For small n, the answer seems to be 1. Gerhard "Ask Me About System Design" Paseman, 2011.08.08 $\endgroup$ – Gerhard Paseman Aug 8 '11 at 16:19

$\begingroup$ Gerhard, one can have two components in $\{0,1\}^4$ already. $\endgroup$ – Gjergji Zaimi Aug 8 '11 at 16:51

$\begingroup$ Indeed Gjergji, also for n=3. I wasn't thinking hard enough when I made the earlier comment. Taking V to be the set of all points with an even number of bits gives the maximum number of connected components; adding 1 more point connects at most n of those components. I originally thought there was a simpler argument to provide a yes answer. I now feel that something like Hall's theorem is needed, after remembering about the V above. Gerhard "Coffee Does Make A Difference" Paseman, 2011.08.08 $\endgroup$ – Gerhard Paseman Aug 8 '11 at 17:21

1$\begingroup$ @domortop: Yes, we can. We get $2^{n2}$ subcubes of size 4 by fixing the first $n2$ coordinates of $H$. Since $V > 2^{n1}$ at least one of these subcubes has 3 points in it. This implies 2 directions. Since we have proof by hand for $n$ up to 5, we can conclude that some component will have 5 directions. $\endgroup$ – Sukhada Fadnavis Aug 10 '11 at 13:59

2$\begingroup$ And how about the (much) weaker assertion that there exists a connected component of size at least $n+1$? (Cf. the case where $V$ consists of all evenweight vertices and just one oddweight vertex.) $\endgroup$ – Seva Aug 10 '11 at 20:14
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
"Bulky subgraphs of the hypercube", by Andrei Kotlov, Europ. J. Combinatorics (2000) 21, 503507
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.

$\begingroup$ I am trying to understand your solution. I suppose, your $d$ is actually the degree if $u$ in the bipartite subgraph, induced by $X$ and $N_G(X)$ (not in $G$), and $N(G)$ was meant to be $N_G(X)$; is this correct? Now, could you explain the conclusion that "the degree of a vertex in $N_G(X)$ is always less than or equal to the degree of its neighbours in $X$"? And, finally, exactly where you use the assumption that none of the connected components has an edge in every direction? Thanks! $\endgroup$ – Seva Aug 8 '11 at 20:52

$\begingroup$ Hi Gjergji, using your notation above, if $x_1, x_2$ are in the same connected component then I don't see why the fourth vertex $v$ should be in $N_G(X)$. Could you please explain? Thanks. $\endgroup$ – Sukhada Fadnavis Aug 9 '11 at 4:33

$\begingroup$ @Sukhada: this is actually easy: if $x_1$ and $x_2$ are both neighbors of $u$, then each of hem differs from $u$ in just one coordinate, and the fourth vertex, say $v$, differs from $u$ in both these coordinates, and differs from each of $x_1$ and $x_2$ in exactly one coordinate; hence $v$ is a neighbor both of $x_1$ and $x_2$. $\endgroup$ – Seva Aug 9 '11 at 7:05

1$\begingroup$ @ Seva. But $v$ may be in $V$, then the edges between $x_1, x_2$ and $v$ don't show up in the induced bipartite graph between $V$ and $H\V$. $\endgroup$ – Sukhada Fadnavis Aug 9 '11 at 7:46

1$\begingroup$ Awesome! Thanks a lot for the answer Gjeirgji :) $\endgroup$ – Sukhada Fadnavis Aug 17 '11 at 18:14