Take the 2-minute tour ×

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 co-ordinate. We say that an edge is in direction $i$ if its endpoints differ in exactly the $i$'th co-ordinate. Suppose $V$ is a subset of $H$ such that $|V| > 2^{n-1}$. Is it true that at least one connected component of the graph induced by $V$ contains edges in all $n$ direction?

share|improve this question
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 –  Gerhard Paseman Aug 8 '11 at 16:19
Gerhard, one can have two components in $\{0,1\}^4$ already. –  Gjergji Zaimi Aug 8 '11 at 16:51
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 –  Gerhard Paseman Aug 8 '11 at 17:21
@domortop: Yes, we can. We get $2^{n-2}$ subcubes of size 4 by fixing the first $n-2$ co-ordinates of $H$. Since $|V| > 2^{n-1}$ 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. –  Sukhada Fadnavis Aug 10 '11 at 13:59
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 even-weight vertices and just one odd-weight vertex.) –  Seva Aug 10 '11 at 20:14

1 Answer 1

up vote 4 down vote accepted

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, 503-507

As far as I can tell from looking at the literature, it is not known if there are configurations of more than $2^{n-1}$ 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.

share|improve this answer
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! –  Seva Aug 8 '11 at 20:52
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. –  Sukhada Fadnavis Aug 9 '11 at 4:33
@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$. –  Seva Aug 9 '11 at 7:05
@ 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$. –  Sukhada Fadnavis Aug 9 '11 at 7:46
Awesome! Thanks a lot for the answer Gjeirgji :) –  Sukhada Fadnavis Aug 17 '11 at 18:14

Your Answer


