# Morphing Hypercubes, Token Sliding and Odd Permutations

A month ago, I asked the following question math.exchange (https://math.stackexchange.com/questions/3127874/morphing-hypercubes-and-odd-permutations), but for completeness, I will include the details here.

Let $$Q_n$$ denote the $$n$$-dimensional hypercube graph -- the graph with vertex set $$V_n = \big\{v : v \in \{0, 1\}^n \big\}$$ and edges $$E_n = \big\{(u,v) : u, v \in V_n \text{ with } u \text{ and } v \text{ having Hamming distance one}\big\}$$

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$$). Every vertex $$v$$ in $$H$$ has a token (or a pebble) with a label $$\ell(v)$$. Next, we 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'$$ is a second parameter.

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 -- in other words, $$H'$$ is the subgraph induced by the vertices from each $$f_i(s_i)$$. If $$H'$$ is also isomorphic to $$Q_{n'}$$, then I call $$H'$$ a $$\texttt{morph}$$ of $$H$$. When a morph operation is applied on $$H$$, the tokens are also moved appropriately.

So my problem is the following. Given $$H$$, I would like to apply/find 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''$$. The caveat is the following: if we consider the permutation induced by the tokens (since the tokens finish on the same subset of vertices that they started on), I want them to induce an odd permutation.

To help clarify, consider the following example with $$n=3$$, $$n'=2$$ and $$d=1$$. Let $$H$$ denote the 2D face of $$Q_3$$ induced by $$0**$$. We place four tokens on those vertices with labels $$A,B,C,D$$ -- $$A$$ is placed on $$000$$, $$B$$ on $$001$$, $$C$$ on $$010$$ and $$D$$ on $$011$$. Now, consider the following three morph operations:

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 map $$00* \to 11*$$ and leave $$01*$$ unchanged (i.e. just apply the identity). This gives us a new graph isomorphic to $$Q_2$$ with token placement $$A$$ on $$110$$, $$B$$ on $$111$$, $$C$$ on $$010$$ and $$D$$ on $$011$$. Note that this new square doesn't have the same "orientation" as the first, since it has a ternary string representation of $$*1*$$.

2) Next, partition the newly obtained $$*1*$$ into $$*10$$ and $$*11$$ -- pairing the tokens $$\{A, C\}$$ and $$\{B, D\}$$. We map $$*10 \to *01$$ to obtain the square $$**1$$ ($$*11$$ is left unchanged). The tokens are located as follows: $$A$$ on $$101$$, $$B$$ on $$111$$, $$C$$ on $$001$$, and $$D$$ on $$011$$.

3) Finally, we partition the obtained $$**1$$ into $$1*1$$ and $$0*1$$ -- pairing the tokens $$\{A,B\}$$ and $$\{C,D\}$$. We map $$1*1 \to 0*0$$, which gives us our graph $$H''$$ induced by the square $$0**$$ (just as it was with $$H$$). If we look at the placement of the tokens, we see that $$A$$ still on $$000$$, $$B$$ is now on $$010$$, $$C$$ is now on $$001$$ and $$D$$ is still on $$111$$. The permutation induced by the new positioning of the tokens is an odd permutation as required.

So now I am interested in the case when $$d=2$$. I would like to find a pair of values for $$n$$ and $$n'$$ where such a sequence of morph operations exist. I don't necessarily want the tightest values of $$n$$ and $$n'$$, nor am I picky about the number of morph operations.

I haven't been able to prove that this is possible, so I have been writing code to perform an "exhaustive search". I can show that this is not possible for values of $$n$$ less than or equal to $$4$$, but the search space grows much to quickly.

So my question is two-fold: 1) What kinds of optimizations should I consider? I am interested in practical heuristics that might help, not necessarily theoretical guarantees, and 2), is there a cleaner way to frame this problem? Just defining what a morph operation is takes a lot of work, let alone the rest.

I apologize for the wall of text, and can try to add missing details or clarifications if necessary.