Induced Cycle Structures of the Hyperoctahedral Group

Source abstract

In this paper, the n-dimensional hypercube $Q_n$ is treated as a graph whose vertex set consists of sequences of 0’s and 1’s of length n, and the hyperoctahedral group $B_n$ is the automorphism group of $Q_n$. It is well known that $B_n$ can be represented by the group of signed permutations, namely, any signed permutation induces a permutation on the vertices of $Q_n$, which preserves adjacency. Moreover, the set of signed permutations on n elements also induces a permutation group on the edges of $Q_n$, denoted $H_n$. The author studies the cycle structures of both $B_n$ and $H_n$. The method proposed here is to determine the induced cycle structure by computing the number of fixed vertices or fixed edges of a signed permutation in the cyclic group generated by a signed permutation of given type. Here we define the type of a signed permutation by a double partition based on its signed cycle decomposition. In this way, one can compute the cycle indices of both $B_n$ and $H_n$ by counting fixed vertices and fixed edges of a signed permutation. The formula for the cycle index of $B_n$ is much more natural and considerably simpler than that of Harrison and High [J. Combin. Theory, 4 (1968), pp. 277–299]. Meanwhile, the cycle structure of $H_n$ seems not to have been studied before, although it is well motivated by nonisomorphic edge colorings of $Q_n$, as well as by the recent interest in edge symmetries of computer networks.