6
$\begingroup$

I'm trying to find out how many ways can I label the nodes of a n dimensional hypercube. The nodes of a n dimensional hypercube can be labelled from 0 to (2^n - 1) in such a way that there is an edge between any two vertices if and only if the binary representations of their labels differ by one and only one bit.

It seems there are a lot of ways to label such a hypercube, but I'm having a hard time formulating it.

I would appreciate your help.

  • 0
    @DimitrijeKostic Jim is right. I wish it w$a$s that sim$p$le, but each node is connected to the nodes that are different from him by one bit only.2011-11-28

2 Answers 2

3

Consider a hypercube canonically embedded into $\mathbb R^n$, such that, in particular, the vertices have coordinates in $\{0,1\}^n$ and the edges are aligned with the coordinate axes. Each coordinate of each vertex can then be naturally represented by a single bit, and two vertices are connected by an edge if and only if their coordinates differ along only one axis.

There are $n!$ ways to map the $n$ coordinate axes to the bits of an $n$-bit string. Furthermore, for each bit, there is a choice of two complementary representations (corresponding to mirroring the hypercube along the axis), for a total of $2^n$ choices. Thus, we have (at least) $n! \cdot 2^n$ distinct ways to map the vertices of an $n$-hypercube onto $n$-bit bitstrings such that adjacent vertices map to strings that differ by one bit.

Showing that these indeed constitute all such mappings is a bit more difficult, but I really just wanted to point out this method of enumerating the mappings for the sake of its nice geometric interpretation.

A related approach is to embed the hypercube into $\mathbb R^n$ such that the vertices lie in $\{-1,1\}^n$, and note that symmetries of the hypercube can then be represented by $n \times n$ signed permutation matrices, which form the hyperoctahedral group of order $n! \cdot 2^n$.

  • 1
    thanks for the explanation. It's a nice approach to solve this problem.2011-11-30
2

In an n-dimensional hypercube there is 2^n nodes each with n neighbours. For the first 2^n bit strings, each node has n neighbours. So you need to show that these determine the same graphs, otherwise the answer is 0.

After that, you can label the first vertice in 2^n ways, and it has n-fold symmetry around each point, so total $n!2^n$ labelings.

Look here for references: http://oeis.org/A000165

  • 0
    @Holowitz thanks.2011-11-30