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?
$\begingroup$
$\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$– Gerhard PasemanCommented Aug 8, 2011 at 16:19
-
$\begingroup$ Gerhard, one can have two components in $\{0,1\}^4$ already. $\endgroup$– Gjergji ZaimiCommented 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$– Gerhard PasemanCommented 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$– Sukhada FadnavisCommented 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$– SevaCommented Aug 10, 2011 at 20:14
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
7
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.
answered Aug 8, 2011 at 15:37
-
$\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$– SevaCommented 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$ Commented 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$– SevaCommented 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$ Commented Aug 9, 2011 at 7:46
-
1$\begingroup$ Awesome! Thanks a lot for the answer Gjeirgji :) $\endgroup$ Commented Aug 17, 2011 at 18:14