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
    57 is the total number of colorings up to rotation, not the colorings such that no two faces with the same color intersect. If you only care about the total number of colorings up to rotation then the answer can be found at http://math.stackexchange.com/questions/5697/coloring-the-faces-of-a-hypercube .2010-11-19
  • 0
    @Jim: I fail to see how two faces of a cube can share a point without also sharing an "edge".2010-11-19
  • 0
    @Jim: that's not true. Take the unit cube representation $[0,1]^n$. Each face is the restriction to either $x_k = 0$ or $x_k = 1$ for some $1\leq k\leq n$. If the two faces are $x_k = 0$ and $x_k = 1$, then clearly they don't intersect. Else you can assume WLOG that they are $x_k = 0$ and $x_j = 0$ for $k\neq j$. They necessarily share the co-dimension two edge $x_k = x_j = 0$. The other way to see it is that at every vertex of the cube, there are $n$ mutually orthogonal directions. Each face that touch that vertex is associated to one direction, its normal. Therefore if two faces touch the2010-11-19
  • 0
    ...same vertex, they must touch at at the span of the $n-2$ vectors that is orthogonal to both normals.2010-11-19
  • 0
    @Willie: Wow, you're right of course. Stupid mistake on my part.2010-11-19
  • 0
    I deleted my comments.2010-11-19
  • 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
    Thanks for the answer. My question was erroneous (not typed as I intended it to be). I am looking at colorings without any intersection condition.2010-11-19
  • 0
    @Timothy: then the answer is given in the question I linked to in the comments, so I will vote to close this question as a duplicate.2010-11-19
  • 0
    Yeah I just read that comment. I shall vote to close too.2010-11-19