4
$\begingroup$

I've tried to count rotationally distinct edge colorings (both proper and improper) in a regular tetrahedron with three colors. Could you take a look if it's correct?

First the improper colorings. There are $3^6$ colorings in all. There are twelve rotations of a tetrahedron:

  • one identity rotation,
  • eight $120^\circ$-rotations around the altitudes,
  • three $180^\circ$-rotations around the the axes of which each intesects two non-intersecting edges in their midpoints.

The identity rotation is okay for every coloring. There are $3^6$ colorings invariant under it.

A $120^\circ$-rotation requires all edges incident with the endpoint of the altitude around which we're rotating to be the same color, and all the rest of the edges to be another color. There are $3^2$ colorings invariant under such a rotation.

The colorings invariant under a $180^\circ$-rotation are such that in the pair of non-intersecting edges defining the rotation, the edges have any colors whatever, and in the other two pairs, both edges have the same color. For any such rotation, there are therefore $3^4$ rotations invariant under it (because we need to color: the first edge in the defining pair, the second edge in it, the edges in the first of the remaining pairs and the edges in the second one).

Therefore, by Burnside's lemma, we have $${1\over12}(1\times3^6+8\times3^2+3\times3^4)=87$$

rotationally distinct, improper edge colorings of a regular tetrahedron with three colors.

For the proper colorings, there are six of them in all. In each of the three pairs of non-intersecting edges, both edges have to be the same color, and each of the pairs has to have a different color. Every such coloring is proper, so there are $3!=6$ proper colorings.

Each of them is invariant under the identity rotation. None of them is invariant under a $120^\circ$-rotation, and all of them are invariant under a $180^\circ$-rotation. Therefore, there are $${1\over 12}(1\times 6+8\times 0+3\times 6)=2$$ rotationally invariant, proper edge colorings of a regular tetrahedron with three colors.

$\endgroup$
1
$\begingroup$

This problem is sufficiently simple that we can solve it without "writing new software" and only having recurse to a CAS for some of the algebra.

We can do both of these by Polya's theorem. First, the improper colorings. We need the cycle index $Z(G_1)$ of the action of the symmetries on the edges. The identity contributes $$a_1^6.$$ Rotations by 120 degrees about an axis connecting a vertex to the center of the opposite face contribute $$8a_3^2.$$ Rotations by 180 degrees about an axis passing through the midpoints of opposite edges fix those edges and pair the remaining ones, to contribute $$3a_1^2 a_2^2.$$

This gives $$Z(G_1) = \frac{1}{12} (a_1^6+8a_3^2+3a_1^2 a_2^2).$$ Substituting with three colors gives $$1/12\, \left( X+Y+Z \right) ^{6}+2/3\, \left( {X}^{3}+{Y}^{3}+{Z}^{3} \right) ^{2}+1/4\, \left( X+Y+Z \right) ^{2} \left( {X}^{2}+{Y}^{2}+{Z}^ {2} \right) ^{2}.$$ Evaluating this at $X=1, Y=1$ and $Z=1,$ we get 87, verifying the first result of the OP.

For the proper colorings, recall that $k$-colorings correspond to partitions into $k$ matchings. There is only one structurally distinct partition into 3 matchings, which pairs opposite edges. The action of the symmetry on these three is as follows: the identity contributes $$a_1^3.$$ The rotations by 120 degrees create a single three-cycle, giving $$8 a_3.$$ Finally and surprisingly, the 180 degree rotations map every matching to itself, giving $$3a_1^3.$$ The cycle index $Z(G_2)$ is $$Z(G_2) = \frac{1}{12} (4a_1^3 + 8a_3).$$ Substituting with three colors now gives $$1/3\, \left( X+Y+Z \right) ^{3}+2/3\,{X}^{3}+2/3\,{Y}^{3}+2/3\,{Z}^{3}$$ or equivalently $${X}^{3}+{X}^{2}Y+{X}^{2}Z+X{Y}^{2}+2\,XYZ+X{Z}^{2}+{Y}^{3}+{Y}^{2}Z+Y{Z}^ {2}+{Z}^{3}.$$ The coefficient of $XYZ$ is $2$, once more confirming the result from the OP.

$\endgroup$
  • $\begingroup$ Thank you. I haven't studied Polya's theorem yet, but I see at least that I got the right numbers, so the method is likely to be OK too. :) What does CAS mean? $\endgroup$ – Bartek Jun 11 '13 at 1:56
  • $\begingroup$ Computer Algebra System. $\endgroup$ – Marko Riedel Jun 11 '13 at 1:57

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.