# #StackBounty: #algorithms #graphs #graph-theory #optimization #heuristics Morphing Hypercubes, Token Sliding and Odd Permutations

### Bounty: 200

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 $$11$$ and $$0$$1\$ — pairing the tokens $${A,B}$$ and $${C,D}$$. We map $$11 to 00$$, 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.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.