3
$\begingroup$

The $n$-dimensional hypercube is vertex transitive. If we define a directed hypercube as an $n$-dimensional hypercube where all of its edges become directed is there a way of orienting the directions such that it still remains vertex transitive?

For example, the $2$-dimensional hypercube is isomorphic to $C_4$. For vertex set $V=\{1,2,3,4\}$ we can define a directed edge set $E=\{(1,2),(2,3),(3,4),(4,1)\}$ one can check to see that this directed cycle is vertex transitive.

On the other hand the $1$-dimensional hypercube is isomorphic to $K_2$. Since $K_2$ has only one edge its directed version can not be vertex transitive (1 vertex will always have an in-going edge and 1 vertex will always have an out-going edge).

In general I suspect that all odd-dimensional directed hypercubes are not vertex transitive (since the number of out-going and in-going edges will be different depending on the vertex) but am unsure about the even-dimensional case.

The question is: Given an even-dimensional hypercube where all of its edges are directed edges is there a way of orienting their directions such that the resulting graph will be vertex transitive?

$\endgroup$

2 Answers 2

2
$\begingroup$

Given directed graphs $G$ and $H$, their Cartesian product $G\times H$ is defined as the graph with vertices $G\times H$, where there is an edge $(g_1,h_1) \to (g_2,h_2)$ if $g_1=g_2$ and $h_1\to h_2$, or if $g_1\to g_2$ and $h_1=h_2$.

Let $\vec B_2$ be a transitive, directed $2\mathrm D$ hypercube: $$ \vec B_2 = \begin{array}{rcl} \bullet & \!\!\!\longrightarrow & \!\!\bullet\\ \big\uparrow & &\!\!\big\downarrow\\ \bullet & \!\!\!\longleftarrow & \!\!\bullet \end{array} $$

Then by the below lemma, $$\overbrace{\vec B_2\times \vec B_2\times\dots\times \vec B_2}^{n\text{ times }}$$ is a transitive, directed $2n$ dimensional hypercube.

Lemma: Let $G$ and $H$ be directed, vertex transitive graphs. Then $G\times H$ is transitive.

Proof: Since $\text{Aut}(G)\times \text{Aut}(H)\subseteq \text{Aut}(G\times H)$, the automorphisms $\phi_G$ and $\phi_H$ bringing $g_1$ to $g_2$ and $h_1$ to $h_2$, respectively, pair to form an automorphism $(\phi_G,\phi_H)$ bringing $(g_1,g_2)$ to $(h_1,h_2)$, proving $G\times H$ is transitive.


$\endgroup$
1
$\begingroup$

As you say, this is only possible when $n$ is even.

When $n=2m$ is even, let the vertices of our hypercube be of the form $(\pm1,\ldots,\pm1)$. Write $J=\pmatrix{0&1\\-1&0}$. Then $J$ has order $4$. Define $G$ to be the group consisting of the block matrices of the form $$\pmatrix{J^{a_1}&&&\\&J^{a_2}&&\\&&\ddots&\\&&&J^{a_m}}.$$ This has $4^m=2^n$ elements, and acts regularly on the vertices of the hypercube.

Now consider the vertex $v_0=(1,1,\ldots,1)$ and also the vertices $w_1,\ldots,w_m$ where $w_j$ is obtained by replacing the $2j$-th entry in $v_0$ by $-1$. Under the action of $G$ the edges $e_j=v_0w_j$ form representatives of the orbits of $G$, and each orbit has $|G|$ elements. Orient $e_j$ from $v_0$ to $w_j$ and use the action of $G$ to orient the other edges (so that each element of $G$ is orientation-preserving). This does it.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .