# Morphing Hypercubes and Odd Permutations

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.