1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.