A Characterization of Planar Caley 2-Color and 3-Color Diagrams, and Their Relationship
to the Archimedean Solids.
by Brian Meneely
Abstract
In this paper we finish a work begun by H. Maschke and published in the American Journal of Mathematics over a century ago (Maschke 1896). We provide a completed proof that, with two exceptions, planar two-color and three-color Cayley diagrams are completely determined by groups associated with the Platonic solids.
Maschke devoted the bulk of this 38 page journal article to proving, in great detail, exactly what geometric qualities a graph would have to have to be both planar and Cayley (either two-color or three-color) at the same time. He determined that, with two exceptions which we will note, all are isomorphic as graphs to one of the Archimedean solids. He then used only two journal pages to simply state that, again with two exceptions, each of these graphs is determined by either a rotational or an extended rotational group associated with one of the Platonic solids. He described generating sets for these groups in purely geometric terms, leaving it to the reader to verify his results. He does not give a clue as to how this could be done, short of brute force, which leads us to believe that this is precisely what Maschke did. We cannot understate what a formidable task this must have been given the (lack of) technology of in Maschke’s day. Even a century after Maschke, we have no general proofs for determining minimal generating sets or the order or products of group elements.
All of the diagrams used in this paper are Maschke’s. We even use the notation on his figures to provide our cyclic notation for the generating sets he describes in purely geometric terms, and to verify the group theoretic properties he attributed to them. We do this using the computer software GAP. To give the reader an idea of the details, the extended rotational group of the octahedron contains 19 elements of order two. Maschke proved that any planar three-color diagram would have to be determined by three generators of order two. Taking these 19 elements, three at a time, yields 969 possibilities sets of three, of which only 312 are generating sets. Grouping these 312 by conjugacy classes yields 9 non-isomorphic Cayley diagrams, only one of which is the planar diagram determined by Maschke. How he may have determined what these generating sets are we will never know. We merely verify them to be correct. We point out that when Maschke described a rotation of a Platonic solid, he never gave a direction for the rotation. We discovered that it makes a difference. We believe, reading things into Maschke’s paper that aren’t stated directly, that he may well have believed it did not. Credence is given to our belief by the fact that Maschek went to the trouble to present a two-color Cayley diagram that is not planar, distinguishing it from one that is only by the order of the generators used to produce it. As we stated above, he could have provided such an example produced by a generating set whose elements matched the order of his and yet produced a non-planar result. By providing no proof of his conjectures, Cayley left the reader uncertain at best as to precisely what generating sets would be responsible for planar Cayley diagrams. With GAP, finding counterexamples to these false generalizations is a trivial matter. We also found two of Maschke’s generating sets to be incorrect (for the extended octahedron and the extended icosahedron). We provide ones that are valid. We believe that we have filled in all of the gaps, and made all of the corrections necessary to complete Maschke’s proof.
To establish his results, Maschke determined that planar two-color and three-color Cayley diagrams associated with finite groups would have to possess certain geometric properties, apart from any particular group that they might represent. He did this by proving first that most such diagrams would have to determine Archimedean solids; and then, by using repeated proofs based entirely on Euler’s theorem (V + F – E = 2), he determined exactly which of these solids they would have to be. Only after he knew what the diagrams would have to be as graphs did he seek the specific groups associated with them. We speculate that he must have been delighted to find that permutation groups determined by the Platonic solids define all the groups so associated.
The commands for GAP that we used to complete Maschke’s proof are remarkably simple. The generators are declared, and the size of the subgroup they generate, viewed as a subgroup of the appropriate symmetric group, is determined. This verifies that the elements are indeed generators of the well- known groups associated with the Platonic solids. The order of their product is then determined as the final step in determining the cycle structure at each vertex, which is compared against the cycle structure of the Archimedean solid in question. We give our results below.
We first describe the exceptions to the rule that the diagrams are all isomorphic as graphs to Archimedean solids. In Figure 11, we see that Maschke associated the dihedral groups with the rotations of a dihedron (a solid determined by a regular n-gon on the equator of a sphere, with an additional vertex at each pole). So that, what we now describe as a reflection on an axis of symmetry on an n-gon, was described by Maschke as a rotation on the same axis that reversed the position of the poles. We will use the word reflection to describe Mashke’s rotation of this type. In Figure 1 and Figure 2, we see the possible two-color Cayley diagrams for the dihedral group of order 6, which can be generalized. Maschke may not have been the first to observe that in every dihedral group of order n there are two elements of order two whose product is order n, but he certainly took the result for granted in his paper, as we see by Figure 1. These two generators of order two are described by Maschke, using our terms, as reflections determined by any two consecutive axes of symmetry of the n-gon determined by the dihedral group. Figure 2, for the dihedral group determined by the triangle in this case, is easily explained in terms of a cyclic element of order n and any reflection. Note, though, that the arrows on the n-cycles are going in opposite directions. If we draw them going in the same direction, the diagram no longer represents a dihedral group, but an abelian group of order 2n (cyclic in the case n is odd).
These take care of the exceptions. The rotation groups of the Platonic solids determine all the remaining planar, two-color, Cayley diagrams. In every case, we will state the generators determined by Maschke, only in terms of permutations based on Maschke’s own diagrams and his geometric description of the movement. The reader may verify, using the computer software GAP, that the elements mentioned do indeed generate the group, as well as produce the necessary cycle structure at each vertex to insure that the two-color Cayley diagram determined by these generators is indeed isomorphic as a graph to the stated Archimedean solid. We group our diagrams by the Platonic solid that determines them. The reader may be interested in viewing the Archimedean solids mentioned. We used names for these objects consistent with those found at the web site: http://www.scienceu.com/geometry/facts/solids/handson.html. This site provides nicely animated graphics and descriptions of each solid. We remind the reader that we are doing things in the reverse order that Maschke did them. He first found the Archimedean solids that could provide planar models for groups and then found the group that produces them. We take the group and identify the generators that will produce a Cayley diagram isomorphic to a given Archimedean solid.
The Tetrahedron:
We refer to Maschke’s Figure 12 to determine our permutations. All quotations are taken from Maschke’s paper.
The rotational group of the tetrahedron produces a two-color Cayley diagram isomorphic to the truncated tetrahedron (Figure 3) by a “rotation of period three passing through vertex 1 and a rotation of period 2 about the diameter bisecting edges 1, 4 and 2,3.” These become the permutations a = (2,3,4) and b = (1,4)(2,3). Their product (we multiply from the left), ab = (1,4,3), is an element of order three that produces the hexagons of alternating colors at each vertex.
The cubeoctahedron (Figure 4)is determined by “the same rotation of period three, and a rotation of period three about the vertex 3.” For these we let a = (2,3,4) and b = (1,2,4). The product a-1b= (1,2)(3,4), has order two and produces the quadrilaterals of alternating color at each vertex. Notice that in these quadrilaterals, the arrows on the sides corresponding to alternating colors change direction, which is why we had to multiply by the inverse of a.
The Octahedron:
We refer to Maschke’s Figure 13 to determine our permutations.
The rotational group of the octahedron produces a two-color Cayley diagram isomorphic to the truncated octahedron (Figure 5) by “a rotation of period 4 about the axis 3, 4 and a rotation of period 2 about the diameter bisecting the edges 4,5 and 3,6. These become the permutations a = (1,6,2,5) and b = (1,2)(3,5)(4,6). Their product ab = (1,4,6)(2,3,5), which has order three and produces the hexagons of alternating color at each vertex.
The truncated cube (Figure 6) is generated by “a rotation of period 3 about the diameter passing through the middle points of the two faces a, and a rotation of period 2 about the diameter bisecting the edges 4-5 and 3-6.” These become permutations a = (1,5,4)(2,6,3) and b = (1,2)(3,6)(4,5). Their product ab= (1,4,2,3) of order 4 produces the octagons of alternating color at each vertex.
The rhombicubeoctahedron (Figure 7) is generated by “the same rotation of period 4 about axis 3, 4 and the same rotation of period 3 about the diameter passing through the middle of the two faces a.” These give us a = (1,6,2,5) and b = (1,5,4)(2,6,3). The
product a-1b= (1,4)(2,3)(5,6) of order 2 produces the quadrilaterals of alternating color at each vertex. Once again notice that in these quadrilaterals, the arrows corresponding to alternating sides change direction.
The Icosahedron:
We refer to Maschke’s Figure 14 to determine our permutations.
The rotational group of the icosahedron produces a two-color Cayley diagram isomorphic to the truncated icosahedron (Figure 8) by “a rotation of period 5 about the diameter passing through vertices 6 and 12, and a rotation of period 2 about the diameter bisecting edges 4-6 and 12-8.” These become permutations a = (1,5,4,3,2)(7,8,9,10,11) and b = (4,6)(8,12)(1,11)(2,10)(7,9)(3,5). Their produce ab = (1,3,10)(2,11,9)(4,5,6)(7,12,8) of order 3 produces the hexagons of alternating colors at each vertex.
The truncated dodecahedron (Figure 9) is generated by “a rotation of period 3 about the diameter passing through the middle of the two faces c, and the rotation of period 2 about the diameter bisection the edges 4-6 and 12-8.” These become permutations a = (1,10,7)(2,5,11)(3,6,4)(8,9,12) and b = (4,6)(8,12)(1,11)(2,10)(7,9)(3,5). Their product ab = (1,2,3,4,5)(7,11,10,9,8) of order 5 produces the 10-gons of alternating colors at each vertex.
The rhombicosidodecahedron (Figure 10) is generated by the “rotation of period 5 about the diameter passing through the vertices 6 and 12, and the rotation of period 3 about the diameter passing through the middle of the two faces c.” These become permutations a = (1,2,3,4,5)(7,11,10,9,8) and b = (1,10,7)(2,5,11)(3,6,4)(8,9,12). The product a-1b = (1,11)(2,10)(3,5)(4,6)(7,9)(8,12) of order 2 produces the quadrilaterals of alternating colors at each vertex, with arrows corresponding to alternating elements pointing in opposite directions.
Conclusions on Planar, Two-Color Cayley
Diagrams:
This completes the characterization of all planar, two-color Cayley diagrams. We have only “modernized” Maschke’s work and provided the reader with the means to verify his proofs, as well as give definiteness to some of his words. In extending his proof to planar, three-color Cayley diagrams, Masche worked differently than in the two-color case. He looked at his two color diagrams, and showed a way to “extend” them to become planar, three-color diagrams for “extensions” of the groups responsible for the two-color diagrams.
We use the Maschke’s term “extended rotation groups” in what follows. By these, he meant the rotation groups associated with each Platonic solid, with reflections through planes of symmetry included. It is a well-know result that these extended groups have orders exactly twice the order of the corresponding rotational group.
Recall that Maschke associated the dihedral groups with the rotations of a dihedron. Thus, we can “extend” these groups as above, by including a reflection through a plane of symmetry. We use Figure 1 to make a generalization. Add a reflection to this group, and we get the three-color Cayley diagram depicted in Figure 16. If we remove one of the colors from Figure 16, and associate vertices corresponding to the endpoints of the removed color, we get either Figure 1 or Figure 2, depending on the color we remove.
Mashke used the example of the extended dihedron groups as a specific case of his more general proof that any planar, three-color Cayley diagram constructed in a similar way would have to be produced by three generators of order 2, and that when certain colors are removed from these three-color diagrams, and vertices associated as above, we would get one of the two-color diagrams already described. Once again, treating the extended dihedron groups as exceptions, Maschke established that all other planar, three-color Cayley diagrams so constructed are isomorphic, as graphs, to Archimedean solids. Furthermore, these diagrams are all determined by extended rotation groups of the Platonic solids. Once again we group our diagrams by the Platonic solid that determines them.
The Extended Tetrahedron:
We refer to Maschke’s Figure 12 to determine our permutations.
The extended group of the tetrahedron produces a three-color Cayley diagram isomorphic to the truncated octahedron (Figure 17) by “a reflection B on the symmetry plane passing through the edge 1-4, the …operation BT, where T represents the rotation of period 2 defined for Figure 3, and the …operation BS, where S represents the rotation of period 3 of Figure 3.” The reflection B we represent with the permutation (2,3). The rotation, T, of period 2 associated with Figure 3 we have already determined to be the permutation (1,4)(2,3), and the rotation, S, as (2,3,4). Letting a = (2,3), b = BT = (1,4), and c = BS = (2,4), we get out three elements of order three. We’ll step you through a typical check on GAP to show that these three elements generate our group, and that their products give us the necessary cycle structure at each vertex. In this case we need a group of order 24, isomorphic to Symmetric Group 4, with pair-wise products having orders 3, 3 and 2 to produce two hexagons and a quadrilateral at each vertex.
gap> a:=(2,3);
(2,3)
gap> b:=(2,4);
(2,4)
gap> c:=(1,4);
(1,4)
gap> TruncatedOctahedron:=Subgroup(SymmetricGroup(4), [a,b,c]);
Group([ (2,3), (2,4), (1,4) ])
gap> Size(TruncatedOctahedron);
24
gap> a*b;
(2,3,4)
gap> a*c;
(1,4)(2,3)
gap> b*c;
(1,4,2)
We see that the deed is done! We believe Maschke would have sold a good deal of his soul for GAP.
We refer to Maschke’s Figure 13 to determine our permutations.
Here’s is where Maschke’s work reveals some remarkable geometric properties of certain Archimedean solids that aren’t normally considered. Referring to Figure 5 and Figure 6, take the squares in the case Figure 5, and the triangles, in the case of Figure 6, and turn them into two-color octagons and hexagons, respectively, by adding alternating sides of a third color. Then take and join the newly created vertices to the corresponding vertex in the adjoining octagon/hexagon in the obvious way using the third color (which previously joined the squares/triangles), to get, in both diagrams, squares. Both Figure 5 and Figure 6 are thus transformed into the rhombitruncated cubeoctahedron of Figure 18. It is perhaps easier to look at things in reverse. If we remove one color from the octagons in Figure 18, we get Figure 5. If we remove one color from the hexagons, we get Figure 6. In either case, we generate Figure 18 by “the rotation T from Figure 5, …the rotation STSST, where S of period 4 is defined by Figure 5 (Maschke’s paper has an error here that we’ve corrected), and the reflection on the symmetry plane passing through the vertices 4,6,3,5.” Letting a = T = (1,2)(3,5)(4,6), S = (1,6,2,5), b = STSST, and c = (1,2), we again let GAP do the dirty work. We need these elements to generate our group of order 48, and have pair-wise produces of orders 2, 3, and 4 to give us our squares, hexagons, and octagons at each vertex of the Cayley diagram. Below we see that these generators do the deed.
gap> a:=(1,2)(3,5)(4,6);
(1,2)(3,5)(4,6)
gap> S:=(1,6,2,5);
(1,6,2,5)
gap> b:=S*a*S*S*a;
(1,6)(2,5)(3,4)
gap> c:=(1,2);
(1,2)
gap> RombitruncatedCuboctahedron:=Subgroup(SymmetricGroup(6),[a,b,c]);
Group([ (1,2)(3,5)(4,6), (1,6)(2,5)(3,4), (1,2) ])
gap> Size(RombitruncatedCuboctahedron);
48
gap> a*b;
(1,5,4)(2,6,3)
gap> a*c;
(3,5)(4,6)
gap> b*c;
(1,6,2,5)(3,4)
The Extended Icosohedron:
We refer to Maschke’s Figure 14 to determine our permutations.
Both Figure 8 and Figure 9 become the rhombitruncated icosohedron (diagram not shown), with its 120 vertices determining a 10-gon, hexagon, and square at each vertex. As above, this can be done by adding a new color and doubling the sides of the pentagons in Figure 8, and the triangles in Figure 9. In either case, we get our generators by “any reflection B on any symmetry plane, the operation BS where S ….(is the operation of order 5 from Figure 8), and BT, where T is the operation of order 2 from Figure 8).” Maschke had enough mistakes in this part of his paper that, were it not for GAP, we would have bailed at this point. As it was, we made some guesses as to what Maschke meant, and GAP showed us to be correct in just a few tries (We guessed and got lucky!). We wish we could make claim to a more reasoned solution. We view this as clear confirmation that Maschke did his proofs by brute force, and that his referees were willing to let his paper ride on its merits at this point. We let a = B = (2,5)(3,4)(8,9)(7,10), S = (1,5,4,3,2)(7,8,9,10,11), T:= (4,6)(8,12)(1,11)(2,10)(7,9)(8,12), b = BS, and c = BT.
gap> a:=(2,5)(3,4)(8,9)(7,10);
( 2, 5)( 3, 4)( 7,10)( 8, 9)
gap> b:=(1,5,4,3,2)(7,8,9,10,11);
( 1, 5, 4, 3, 2)( 7, 8, 9,10,11)
gap> c:=(4,6)(8,12)(1,11)(2,10)(7,9)(3,5);
( 1,11)( 2,10)( 3, 5)( 4, 6)( 7, 9)( 8,12)
gap> RhombitruncatedIcosohedron:=Subgroup(SymmetricGroup(12), [a,b,c
Group([ ( 2, 5)( 3, 4)( 7,10)( 8, 9), ( 1, 5, 4, 3, 2)( 7, 8, 9,10,1
( 1,11)( 2,10)( 3, 5)( 4, 6)( 7, 9)( 8,12) ])
gap> Size(RhombitruncatedIcosohedron);
120
gap> b:=a*b;
( 1, 5)( 2, 4)( 7,11)( 8,10)
gap> c:=a*c;
( 1,11)( 2, 3, 6, 4, 5,10, 9,12, 8, 7)
gap> a*b;
( 1, 5, 4, 3, 2)( 7, 8, 9,10,11)
gap> a*c;
( 1,11)( 2,10)( 3, 5)( 4, 6)( 7, 9)( 8,12)
gap> b*c;
( 1,10, 7)( 2, 5,11)( 3, 6, 4)( 8, 9,12)
Conclusions on Planar, Three-Color Cayley
Diagrams:
Unlike the two-color case, we cannot be
certain that we have completely characterized all planar Cayley
three-color diagrams. We have found only
those determined by the extended rotation groups on the Platonic solids,
establishing a relationship between the Platonic and the Archimedean solids
that couldn’t have even been imagined by the mathematicians who first studied
these objects. The proof was done by “extending”
certain two-color diagrams, which does leave open the possibility that there
could be others. We make the conjecture
that there are not. We leave the matter
here.
Maschke, H. (1896). "The Representation of Finite Groups, especially of the Rotation Groups of the Regular Bodies of Three- and Four-dimensional Space, by Cayley's Color Diagrams." American Journal of Mathematics 18: 156-194.
