#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 $01$ — 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!!!

Leave a Reply

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