1
$\begingroup$

I was wondering if there are any general results to this problem. Explicitly, given an $n$-cube and $n$ distinct colors, in how many ways can we paint the faces of the cube. Here we consider two colorings the same if they can be obtained from one another by rotations.

For $n=3$ this number is $57$ by Burnside's lemma.

Are there any results for higher dimensions?

Edit: Thanks for all the comments and sorry for the errors in my question. There is no intersection condition.

  • 0
    @Qiachu: Thanks for the link.2010-11-19

1 Answers 1

3

The answer is $1$ in all dimensions, if you mean what I think you mean by "faces."

The underlying graph you're trying to color is the graph whose vertices are the points $(\pm 1, 0, 0, ...), (0, \pm 1, 0, ...), ...$ where a vertex is adjacent to every other vertex except the opposite one (and note that by "vertex" here I mean "face of an $n$-cube"); in other words it is the Turan graph $T_2(2n)$. In particular the subgraph formed by $(1, 0, 0, ...), (0, 1, 0, ...), ...$ is a $K_n$, so we must use each of the $n$ colors exactly once to color each of these vertices. But now it's not hard to see that, since a vertex and its opposite share the same neighbors, they must have the same color. So the only valid colorings are those which use each of the $n$ colors exactly twice each, once for each pair of opposite vertices.

Now every permutation of the set of pairs of opposite vertices is realizable by a rotation, and it follows that the coloring is unique up to rotation.

  • 0
    Yeah I just read that comment. I shall vote to close too.2010-11-19