Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
If you're asking how many ways you can assign the numbers $0, \dots, 2^n-1$ to the vertices of a hypercube, it's simply $(2^n)!$. –  Dimitrije Kostic Nov 28 '11 at 15:21
    
@DimitrijeKostic: That's not what he's asking. Vertices connected by an edge need to differ by only one bit. –  Grumpy Parsnip Nov 28 '11 at 15:32
    
@DimitrijeKostic Jim is right. I wish it was that simple, but each node is connected to the nodes that are different from him by one bit only. –  Maynard Nov 28 '11 at 15:55

2 Answers 2

up vote 3 down vote accepted

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$.

share|improve this answer
1  
thanks for the explanation. It's a nice approach to solve this problem. –  Maynard Nov 30 '11 at 21:11

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

share|improve this answer
    
Alternatively, view each labelling as an automorphism of the hypercube graph (mapping some canonical labelling of the vertices to the current one). Harary published a paper called The Automorphism Group of a Hypercube in JUCS in 2000, which constructs the group explicitly (and gives the same result for its size). –  Erik P. Nov 28 '11 at 17:06
    
@Holowitz thanks. –  Maynard Nov 30 '11 at 21:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.