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.

  • $\begingroup$ 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 math.stackexchange.com/questions/5697/… . $\endgroup$ – Qiaochu Yuan Nov 19 '10 at 15:45
  • $\begingroup$ @Jim: I fail to see how two faces of a cube can share a point without also sharing an "edge". $\endgroup$ – Willie Wong Nov 19 '10 at 16:31
  • $\begingroup$ @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 the $\endgroup$ – Willie Wong Nov 19 '10 at 17:06
  • $\begingroup$ ...same vertex, they must touch at at the span of the $n-2$ vectors that is orthogonal to both normals. $\endgroup$ – Willie Wong Nov 19 '10 at 17:10
  • $\begingroup$ @Willie: Wow, you're right of course. Stupid mistake on my part. $\endgroup$ – Cheerful Parsnip Nov 19 '10 at 17:19

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.

  • $\begingroup$ 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. $\endgroup$ – Timothy Wagner Nov 19 '10 at 17:15
  • $\begingroup$ @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. $\endgroup$ – Qiaochu Yuan Nov 19 '10 at 17:21
  • $\begingroup$ Yeah I just read that comment. I shall vote to close too. $\endgroup$ – Timothy Wagner Nov 19 '10 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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