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?

  • 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^{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. $\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 even-weight vertices and just one odd-weight 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, 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.

  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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