4
$\begingroup$

Let $Q_n$ denote the $n$-dimensional hypercube graph and let $H$ denote a subgraph of $Q_n$ that is isomorphic to $Q_{n'}$, for some input parameter $n' \leq n$ (i.e. $H$ is an $n'$-dimensional subcube of $Q_n$). Next, I would like to partition $H$ into $2^{n' - d}$ vertex disjoint subgraphs $H_1, \ldots, H_{2^{n'-d}}$ each isomorphic to $Q_d$ where $d \leq n'$.

We can think of each $H_i$ as a ternary string $s_i \in \{0, 1, *\}^n$ such that $s_i$ has exactly $d$ $*$'s. These represent free coordinates. For each $s_i$, we define a mapping $f_i : \{0, 1, *\}^n \to \{0, 1, *\}^n$ such that the $j$-th coordinate of $f_i(s_i)$ is a $*$ if and only if the $j$-th coordinate of $s_i$ is a $*$. So intuitively, each $f_i$ maps a $d$-dimensional subcube to another $d$-dimensional subcube on the same axes. Let $H'$ denote the subgraph obtained by decomposing $H$ as described above and applying the $f_i$'s on its $2^{n'-d}$ pieces. If $H'$ is also isomorphic to $Q_{n'}$, then I call $H'$ a "morph" of $H$.

So my question is the following. Given $H$, I would like to apply a sequence of "morph" operations to obtain a graph $H''$ that "finishes where $H$ started". By this, I mean that the ternary string that represents $H$ must be the same as $H''$. However, if we look at the placement of the vertices in $H$ and $H''$, I want them to induce an odd permutation.

To make things clearer, let's look at a small example. Let $H$ denote a subgraph isomorphic to $Q_2$ in $Q_3$. In my example, I will take $H$ to be the graph induced by the vertices with labels $\{A=000, B=001, C=010, D=011\}$ (i.e. the $0**$ face of $Q_3$). Now, consider the following 3 morph operations when $d=1$:

1) Partition $\{A,B,C,D\}$ into pairs $\{A,B\}$ and $\{C, D\}$. These can be represented by ternary strings $00*$ and $01*$ respectively.We morph $00* \to 11*$ and leave $01*$ unchanged. This gives us a new graph isomorphic to $Q_2$ with vertices $\{A = 110, B = 111, C = 010, D = 011\}$. Note that $C$ and $D$ are unchaged from before. This new square doesn't have the same "orientation" as the first, since it has ternary string $*1*$.

2) Next, partition the newly obtained $*1*$ into $*10$ and $*11$ and we morph $*10 \to *01$ to obtain the square $**1$ with labels $\{A = 101, B = 111, C = 001, D = 011\}$. This also doesn't have the same "orientation" as $H$.

3) Finally, we partition the obtained $**1$ into $1*1$ and $0*1$ and morph $1*1 \to 0*0$. This gives us our graph $H''$ induced by the square $0**$ (just as it was with $H$). However, if we look at the new label placements, we see that we have $\{A = 000, B = 010, C = 001, D=011\}$. And if we look at the permutation induced by $A,B,C,D$, we see that: $A$ went from $000$ to $000$, $B$ from $001$ to $010$, $C$ went from $010$ to $001$ and $D$ went from $011$ to $011$. This permutation is an odd permutation as needed.

So now I am interested in the case when $d=2$. Does there exists an $n'$ and $n$ such that there is a sequence of such "morph" operations that induce an odd permutation?

I can try to add additional details if the question is still unclear. I also apologize for using possibly faulty terminology... I don't know the best way to frame/word this problem. Is there a better way to frame this problem?

Edit: I've updated the labels for the vertices from a,b,c,d to A,B,C,D to avoid confusion with the other parameter d.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.