Is this graph coloring problem solved correctly?

296 Views Asked by At

On this Wikipedia page about Burnside's lemma, it is calculated that there are 57 rotationally distinct colorings of the faces of a cube with three colors. I'm confused by the way it is done.

They apply the lemma to the set of all $3^6$ functions assigning one color to every face. Is it correct? The page about graph colorings says that a face coloring is one in which no two neighboring faces have the same color. It seems to me that the proof here disregards this definition. How should I understand this? What is calculated here? And how do I calculate the other thing?

1

There are 1 best solutions below

1
On BEST ANSWER

Let's call a face-coloring "proper" if no two neighboring faces have the same color, "improper" otherwise. The $57$ rotationally distinct face-colorings of the cube include improper colorings and colorings which do not use all three of the available colors, e.g., they include the $3$ colorings in which all faces have the same color.

If you want to count the rotationally distinct proper face-colorings of the cube with $3$ colors, you can use Burnside's theorem if you want to, or you can count them by hand. In fact, there is only one way to do it, because opposite faces must have the same color.

On the Wikipedia page about Burnside's lemma, the number of rotationally distinct colorings (not necessarily proper) is calculated as $$\frac 1{24}(1\times3^6+6\times 3^3+3\times 3^4+8\times 3^2+6\times 3^3)=57.$$ For proper colorings this becomes $$\frac 1{24}(1\times 6+6\times 0+3\times 6+8\times 0+6\times 0)=1.$$ In the first term of the "improper" formula, the factor $1$ is the number of identity rotations, the factor $3^6$ is the number of colorings which are invariant under the identity rotation, which means all of them. In the corresponding term of the "proper" formula, the factor $3^6$ is replaced by the number of proper colorings, which is $3\times 2=6$ since the whole coloring is determined once two neighboring faces have been colored.

In the second term of the "improper" formula, the factor $6$ is the number of $90$ degree face rotations, and the factor $3^3$ is the number of colorings invariant under a given rotation of that type. E.g., for a 90 degree rotation about the vertical axis through the center of the cube, the invariant colorings are those in which the four vertical faces have the same color. None of these are proper colorings, so the corresponding factor in the "proper" formula is $0$.