# Edge coloring of the cube

We have a cube and we are coloring its edges. There are three colors available. We say that the two colorings are the same if one can obtain a second by turning cube and permuting colors. Find the number of different colorings.

Any ideas?

I've found Pólya enumeration theorem, but it's difficult to understand for me, also this approach does not take into account the permutation of colors...

-

As I started working on this using Burnside's lemma, I might as well show what I've got. It is easy to make a mistake here, so no guarantees. At least I got an answer that passes the lithmus test of being an integer:-)

As described in loc.cit the 24 rotations of the cube split into 5 conjugacy classes. For each class we need to know what kind of orbits a representative in that class (or rather, the cyclic group generated by the representative) has among the edges. We also need to know the cardinality of the class.

$A$: The class of the identity mapping. Its action on the edges has 12 singleton orbits, and $|A|=1$.

$B$: The class of 90 degree rotations. Its action partitions the edges into 3 orbits with 4 edges in each orbit. $|B|=6.$

$C$: The class of 180 degree rotations about an axis connecting the midpoints of an opposite pair of faces of the cube (the squares of elements of class $B$). The edges are partitioned into 6 pairs. $|C|=3.$

$D$: The class of 120 degree rotations about an axis connecting two opposite vertices. The edges are partitioned to 4 orbits, each with 3 edges. $|D|=8.$

$E$: The class of 180 degree rotations about an axis connecting the midpoints of two parallel but opposite edges. The edges are partitioned into 7 orbits: 2 singletons (the ones intersecting the axis) and 5 pairs. $|E|=6.$

The group of color permutations is isomorphic to $S_3$ and has three conjugacy classes: $a$= the class of the identity mapping, $b$= the class of three 2-cycles (this time swapping two colors and leaving the third color as it is), $c$= the class of two 3-cycles.

The cartesian product of order $24\cdot6=144$ then acts on the set $X$ of colorings. The following table lists the number of fixed points in $X$ that an element of the listed conjugacy class has.

$$\begin{array}{c|c|ccc|c|c} \text{class}&\text{size}&|X^g|&&\text{class}&\text{size}&|X^g|\\ \hline Aa&1&3^{12}&&Cc&6&0\\ Ab&3&1&&Da&8&3^4\\ Ac&2&0&&Db&24&1\\ Ba&6&3^3&&Dc&16&3^4\\ Bb&18&3^3&&Ea&6&3^7\\ Bc&12&0&&Eb&18&3^5\\ Ca&3&3^6&&Ec&12&0\\ Cb&9&3^6&&&& \end{array}$$ Feeding these numbers into the formula of Burnside's lemma tells that the number of orbits (=the number of distinguishable colorings under the prescribed rules) is $$|X/G|=\frac{1\cdot3^{12}+3\cdot1+6\cdot3^3+18\cdot3^3+3\cdot3^6+9\cdot3^6+8\cdot3^4+24\cdot1+16\cdot3^4+6\cdot3^7+18\cdot3^5}{144}=3882.$$

How did I come up with these numbers. The details vary a bit case-by-case. As somewhat typical examples consider:

The class $Ab$: Here the edges stay at the same place, but two of the colors are interchanged. A coloring is a fixed point of this operation only if it is monochromatic (of the non-interchanged color). Thus the elements in this class have exactly one fixed point.

The class $Ba$: Here we want to calculate the number of colorings that remain unchanged, when we rotate the cube by 90 degrees, and don't do any repainting. For this to happen it is necessary and sufficient that any of the three groups of four edges permuted among themselves by the rotation must share the same color. We have the liberty of choosing the colors for all the orbits independently. Therefore there are $3^3$ such colorings.

The class $Bb$: Here the 3 groups of 4 edges undergo some repainting in addition to the 90 degree rotation. If the three colors are R,Y,G, and we are to repaint every yellow edge green, and every green edge yellow, then for each orbit the possible colorings are RRRR, YGYG and GYGY. In the latter two cases repainting cancels the effect of the rotation. So we have 3 choice for the three groups of 4 edges, and a total of $3^3$ colorings fixed under a group action of this type.

The class $Bc$: Here we can assume a color replacement scheme $Y\mapsto R\mapsto G\mapsto Y$. This permutation of order 3 just doesn't mesh with the rotation of order 4, so no colorings are fixed points for this operation.

The class $Dc$: Let's study the same color replacement scheme as with class $Bc$. The 12 edges are partitioned into 4 groups of 3 edges. The coloring of such a group has to be either $RGY$, $GYR$ or $YRG$ for the repainting to cancel the effect of the rotation. But the choices for the four orbits are independent from each other, so we get a total of $3^4$ colorings that are fixed under an operation of this type.

The class $Eb$: Assume color replacement scheme $R\mapsto R$, $Y\mapsto G\mapsto Y$. For a coloring to be a fixed point, the two edges that are rotated in place, must both be red. But for the 5 pairs of edgese that interchange their locations, the possible colorings are $RR$, $YG$ and $GY$ for the same reasons as with class $Bb$.

If you have trouble filling in the rest of the table, @ping me!

-
Addendum: Jyrki has done a very thorough discussion of the fixed points of edge colorings under various actions, and I have nothing much to add to his excellent explanantion except that it is often only little more work to do the analysis in general for $N$ colors, and to get a polynomial in $N$, than it is to do it for some particular $N$, as Jyrki did.
I don't see, why we would get a polynomial in $N$ as a solution to the $N$-colored version of this problem? Are you saying that it is not just a coincidence, that we got a power of 3 e.g. in the case Bb? May be it isn't? I'll give you a bounty, if you can derive a general formula here (that is, without consuming a full paper's worth of space)!! I would have guessed that the number of conjugacy classess of $S_N$ blowing on your face alone would make it mighty hard. +1 for the link to your blog was already there :-) –  Jyrki Lahtonen May 29 '12 at 8:58
@Jyrki: The solution isn't a polynomial in $N$ because it's constant for $N\ge12$ but not constant for $N\le12$. (By the way, that also means it's easy to derive a general formula, since one would merely have to write a program that counts the patterns up to $N=12$. :-) –  joriki Feb 3 '13 at 14:12