5
$\begingroup$

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?

$\endgroup$
11
  • 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$ Aug 8, 2011 at 16:19
  • $\begingroup$ Gerhard, one can have two components in $\{0,1\}^4$ already. $\endgroup$ Aug 8, 2011 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$ Aug 8, 2011 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$ Aug 10, 2011 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, 2011 at 20:14

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
7
  • $\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, 2011 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$ Aug 9, 2011 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, 2011 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$ Aug 9, 2011 at 7:46
  • 1
    $\begingroup$ Awesome! Thanks a lot for the answer Gjeirgji :) $\endgroup$ Aug 17, 2011 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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