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\}$. This also doesn't have the same "orientation" as $H$.

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. Is there a better way to frame this problem?

Edit: I've updated the labels for the vertices from a,b,c,d to A,B,C,D to avoid confusion with the other parameter d.


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.