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\}$ .

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.