Given $n\geq 2$, let us consider the n-cube $H_n=(V,E)$, i.e. vertex set $V$ is $\{0,1\}^n$. Here, the edges of $H_n$ are directed, oriented by set inclusion, i.e., $(x,y)\in E$ iff $x\subseteq y$ and $\text{dist}_{Hamm}(x,y)=1$). Let $0^n := (0, 0, \ldots, 0)$ and $1^n := (1, 1, \ldots, 1)$. Let $S\subseteq V\setminus \{0^n, 1^n\}$ such that $|S|=n$. Assume that in $H_n\setminus S$ there is no directed path from $0^n$ to $1^n$. Then, is it true that $H_n\setminus S$, now viewed as undirected graph, is disconnected (i.e. "no directed path" implies "no undirected path" in this setting) ?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What is the orientation of the edges, even for $H_3$? The $n-1$ dimensional faces of $H_n$ inherit an orientation from $H_n$, but already the $n-2$ dimensional edges inherit opposite orientations from the two adjacent $n-1$ dimensional faces. Also, do you want to assume $0^n,1^n\notin S$? $\endgroup$– Joonas IlmavirtaCommented Nov 27, 2014 at 9:49
-
$\begingroup$ the orientation is by set inclusion: (x,y)\in E iff x\subset y and hamming_dist(x,y)=1. And yes $0^n,1^n$ are not in $S$. Thank you. $\endgroup$– XorwellCommented Nov 27, 2014 at 9:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Every vertex removed from the $k$th layer prohibits $k!(n-k)!\leq (n-1)!$ paths. Thus, if $n$ removed verices prohibit all $n!$ paths, then each of them prohibits exactly $(n-1)!$ paths, and the sets of prohibited paths are disjoint. This means that either all the vertices are on the first layer, or all the vertices are on the $(n-1)$th layer. In both cases their removal disconnects the unoriented graph as well.
-
$\begingroup$ I think so, thanks for confirming Ilya. $\endgroup$– XorwellCommented Nov 27, 2014 at 10:26