2
$\begingroup$

I am looking for ways to color a truncated tetrahedron allowing rotations and reflections. I know the ways to color a tetrahedron in a similar way but stumped on this. From wikipedia, both tetrahedron and truncated tetrahedron have same symmetry groups so I think this can help in reaching an answer.

Also, if there are links that discuss the coloring of truncated objects like truncated cube, truncated octahedral and also for cuboctahedron, that would be very helpful. Thanks!

$\endgroup$
  • $\begingroup$ I think I misunderstood initially. You're looking to count the number of distinct colorings of a truncated tetrahedron, taking symmetries into account? $\endgroup$ – pjs36 Jul 10 '16 at 13:14
  • 1
    $\begingroup$ @pjs36 Yes and if possible, for other truncated objects too. :) $\endgroup$ – user352836 Jul 10 '16 at 13:15
0
$\begingroup$

Introductory remark. With this problem I strongly urge the reader to verify this calculation including by enumeration which can be an interesting coding challenge.

Suppose we start from a tretrahedron with vertices labeled $1,2,3,4.$ Observe that the rotational symmetries consist of the identity, rotations about an axis connecting a vertex to the center of the opposite face and rotations about an axis passing through the midpoint of two opposite edges. These can be combined with a reflection. We thus obtain for the total number of symmetries

$$2\times(1+ 4\times 2 + 3) = 24$$

which means the symmetries of the tetrahedron are the symmetric group $S_4$ consisting of all permutations of the four vertices. Now for the cycle indices of the action on vertices and faces in the case of the truncated tetrahedron we must decide on a canonical labeling of the vertices and the faces. For the vertices we label them with the edge of the original tetrahedron that they are located on and the vertex they are closest to.

$$[\{1,2\}, 1], [\{1,2\}, 2], [\{1,3\}, 1], [\{1,3\}, 3], [\{1,4\}, 1], [\{1,4\}, 4], \\ [\{2,3\}, 2], [\{2,3\}, 3], [\{2,4\}, 2], [\{2,4\}, 4], [\{3,4\}, 3], [\{3, 4\}, 4].$$

Letting the permutations of $S_4$ act on these and factoring the result into cycles yields the following cycle index:

$$1/24\,{a_{{1}}}^{12}+1/4\,{a_{{1}}}^{2}{a_{{2}}}^{5} +1/8\,{a_{{2}}}^{6}+1/3\,{a_{{3}}}^{4}+1/4\,{a_{{4}}}^{3}.$$

and for vertex colorings of at most $n$ colors

$$1, 218, 22815, 703760, 10194250, 90775566, 576941778, \\ 2863870080, 11769161895, 41669295250,\ldots$$

the closed form being

$$1/24\,{n}^{12}+1/4\,{n}^{7}+1/8\,{n}^{6}+1/3\,{n}^{4} +1/4\,{n}^{3}$$

which points us to OEIS A060530, where we find it listed as edge colorings of the cube. This is because the rotational symmetries of the cube establish any permutation of the four diagonals, an isomorphism with $S_4.$

Coloring faces is much simpler and could be done manually but we will re-use the software we already have. For the canonical labeling of the faces we label the triangular faces with the number of the vertex that was present before truncation and the hexagonal ones with the three vertices that formed the source face which into which the hexagon is embedded. We thus obtain

$$1,2,3,4 \quad\text{and}\quad \{1,2,3\}, \{1,2,4\}, \{2,3,4\}, \{1,3,4\}.$$

We get the cycle index

$$1/24\,{a_{{1}}}^{8}+1/4\,{a_{{1}}}^{4}{a_{{2}}}^{2} +1/3\,{a_{{1}}}^{2}{a_{{3}}}^{2} +1/8\,{a_{{2}}}^{4}+1/4\,{a_{{4}}}^{2}$$

and the sequence

$$1, 35, 495, 3876, 20475, 82251, 270725, 766480, \\ 1929501, 4421275,\ldots$$

the closed form being

$$1/24\,{n}^{8}+1/4\,{n}^{6}+{\frac {11\,{n}^{4}}{24}} +1/4\,{n}^{2}$$

which is not yet included in the OEIS.

The coefficients on these cycle indices suggest there is a better way to compute them starting from the shared symmetry between the two problems. (These are the coefficients of the terms in $Z(S_4).$) This is left to the reader.

The Maple code for this computation goes as follows.

with(combinat);

pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;

    numsubs := [seq(src[k]=k, k=1..nops(src))];
    numa := subs(numsubs, aut);

    marks := Array([seq(true, pos=1..nops(aut))]);

    cycs := []; pos := 1;

    while pos <= nops(aut) do
        if marks[pos] then
            clen := 0; cpos := pos;

            while marks[cpos] do
                marks[cpos] := false;
                cpos := numa[cpos];
                clen := clen+1;
            od;

            cycs := [op(cycs), clen];
        fi;

        pos := pos+1;
    od;

    return mul(a[cycs[k]], k=1..nops(cycs));
end;

pet_cycleind_t4h_verts :=
proc()
local perm, cind, verts, vperm;
    cind := 0;

    verts :=
    [[{1,2}, 1], [{1,2}, 2],
     [{1,3}, 1], [{1,3}, 3],
     [{1,4}, 1], [{1,4}, 4],
     [{2,3}, 2], [{2,3}, 3],
     [{2,4}, 2], [{2,4}, 4],
     [{3,4}, 3], [{3,4}, 4]];


    for perm in permute(4) do
        vperm :=
        subs([seq(q=perm[q], q=1..4)], verts);

        cind := cind +
        pet_autom2cycles(verts, vperm);
    od;

    cind/24;
end;

pet_cycleind_t4h_faces :=
proc()
local perm, cind, faces, fperm;
    cind := 0;

    faces :=
    [1,2,3,4,
     {1,2,3}, {1,2,4},
     {2,3,4}, {1,3,4}];

    for perm in permute(4) do
        fperm :=
        subs([seq(q=perm[q], q=1..4)], faces);

        cind := cind +
        pet_autom2cycles(faces, fperm);
    od;

    cind/24;
end;

Xverts :=
subs([seq(a[q]=n, q=1..12)], pet_cycleind_t4h_verts());

Xfaces :=
subs([seq(a[q]=n, q=1..8)], pet_cycleind_t4h_faces());

With these colorings we assume that the available colors are the same no matter the type of the face (triangular or hexagonal).

Addendum. Using the very same method as above we can also compute the cycle indices for the action on the faces and vertices of the truncated cube (triangular and octagonal). These get more difficult to handle manually as the number of vertices increases. The key obervation here is that the full symmetries of the cube are realized by labeling the vertices with $3$ bits (from zero to seven, or equivalently if a zero label is not desired from one to eight) where vertices are adjacent if they differ in exactly one bit. The symmetries are then obtained by combining a permutation of the bits with a bit flip according to eight possible bit masks. This is quite straightforward.

We obtain for the vertices the cycle index

$$1/48\,{a_{{1}}}^{24}+1/8\,{a_{{2}}}^{10}{a_{{1}}}^{4} +{\frac {13\,{a_{{2}}}^{12}}{48}}+1/6\,{a_{{3}}}^{8} +1/4\,{a_{{4}}}^{6}+1/6\,{a_{{6}}}^{4}$$

and the closed form

$$1/48\,{n}^{24}+1/8\,{n}^{14}+{\frac {13\,{n}^{12}}{48}} +1/6\,{n}^{8}+1/4\,{n}^{6}+1/6\,{n}^{4}.$$

For the faces we get the cycle index

$$1/48\,{a_{{1}}}^{14}+1/8\,{a_{{1}}}^{6}{a_{{2}}}^{4} +1/16\,{a_{{2}}}^{5}{a_{{1}}}^{4}+1/16\,{a_{{2}}}^{6}{a_{{1}}}^{2} \\+{\frac {7\,{a_{{2}}}^{7}}{48}}+1/6\,{a_{{1}}}^{2}{a_{{3}}}^{4} +1/8\,{a_{{4}}}^{3}{a_{{1}}}^{2} \\+1/8\,{a_{{4}}}^{3}a_{{2}}+1/6\,{a_{{6}}}^{2}a_{{2}}$$

and the closed form

$$1/48\,{n}^{14}+1/8\,{n}^{10}+1/16\,{n}^{9}+1/16\,{n}^{8} \\+{\frac {7\,{n}^{7}}{48}}+1/6\,{n}^{6}+1/8\,{n}^{5} +1/8\,{n}^{4}+1/6\,{n}^{3}.$$

The Maple code for this goes as follows.

with(combinat);

pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;

    numsubs := [seq(src[k]=k, k=1..nops(src))];
    numa := subs(numsubs, aut);

    marks := Array([seq(true, pos=1..nops(aut))]);

    cycs := []; pos := 1;

    while pos <= nops(aut) do
        if marks[pos] then
            clen := 0; cpos := pos;

            while marks[cpos] do
                marks[cpos] := false;
                cpos := numa[cpos];
                clen := clen+1;
            od;

            cycs := [op(cycs), clen];
        fi;

        pos := pos+1;
    od;

    return mul(a[cycs[k]], k=1..nops(cycs));
end;

pet_cube_symact :=
proc(cv, symp, symf)
local bincbverts, bin, f;
    bincbverts :=
    [[0,0,0], [0,0,1], [0,1,0], [0,1,1],
     [1,0,0], [1,0,1], [1,1,0], [1,1,1]];


    bin := bincbverts[cv];
    bin := [seq(bin[symp[q]], q=1..3)];

    for f to 3 do
        if f in symf then
            bin[f] := 1 - bin[f];
        fi;
    od;

    1 + bin[1]*4 + bin[2]*2 + bin[3];
end;


pet_cycleind_tcube_verts :=
proc()
local bincbverts, cbedg, sl,
    perm, flip, cind, verts, vperm;

    cbedg :=
    [{1,2}, {1,3}, {1,5},
     {2,4}, {2,6}, {3,4},
     {3,7}, {4,8}, {5,6},
     {5,7}, {6,8}, {7,8}];

    verts :=
    [seq(seq([edg, v], v in edg),
         edg in cbedg)];

    cind := 0;

    for perm in permute(3) do
        for flip in powerset(3) do
            sl :=
            [seq(q=pet_cube_symact(q, perm, flip),
                 q=1..8)];

            vperm := subs(sl, verts);

            cind := cind +
            pet_autom2cycles(verts, vperm);
        od;
    od;

    cind/48;
end;


pet_cycleind_tcube_faces :=
proc()
local perm, flip, cind, sl, faces, fperm;
    cind := 0;

    faces :=
    [1,2,3,4,5,6,7,8,
     {1,2,3,4}, {1,2,5,6},
     {2,4,6,8}, {1,3,5,7},
     {3,4,7,8}, {5,6,7,8}];

    for perm in permute(3) do
        for flip in powerset(3) do
            sl :=
            [seq(q=pet_cube_symact(q, perm, flip),
                 q=1..8)];

            fperm := subs(sl, faces);

            cind := cind +
            pet_autom2cycles(faces, fperm);
        od;
    od;

    cind/48;
end;

Xverts :=
subs([seq(a[q]=n, q=1..24)], pet_cycleind_tcube_verts());

Xfaces :=
subs([seq(a[q]=n, q=1..14)], pet_cycleind_tcube_faces());

Completion of task. We can also color the $36$ edges of the truncated cube. The symmetries that act are of course the same as before and we encode the edges by a simple scheme -- use the source edge from the cube for the edges that appear in the center of an edge of the cube and use a pair of source edges to indicate an edge that appeared due to truncation, with the common vertex having been truncated. Observe that we may well ask whether a fourty-five degree rotation about an axis connecting two opposite octagonal faces contributes to the symmetries. It does not, however, because it only fixes those two faces and the triangular as well as the remaining octagonal faces are left without an image. (In fact one can also argue that this would attempt to map an edge of length one to an edge of length $\sqrt{2}.$)

We get the following cycle index:

$$1/48\,{a_{{1}}}^{36}+1/8\,{a_{{2}}}^{15}{a_{{1}}}^{6} \\+1/16\,{a_{{1}}}^{4}{a_{{2}}}^{16} +1/8\,{a_{{2}}}^{17}{a_{{1}}}^{2}+1/12\,{a_{{2}}}^{18} \\ +1/6\,{a_{{3}}}^{12}+1/4\,{a_{{4}}}^{9}+1/6\,{a_{{6}}}^{6}.$$

The closed form is

$$1/48\,{n}^{36}+1/8\,{n}^{21}+1/16\,{n}^{20}+1/8\,{n}^{19} \\+1/12\,{n}^{18}+1/6\,{n}^{12}+1/4\,{n}^{9}+1/6\,{n}^{6}.$$

The Maple code was

# common routine omitted

pet_cycleind_tcube_edges :=
proc()
local bincbverts, cbedg, sl,
    perm, flip, cind, edges, eperm, e1, e2, f1, f2;

    cbedg :=
    [{1,2}, {1,3}, {1,5},
     {2,4}, {2,6}, {3,4},
     {3,7}, {4,8}, {5,6},
     {5,7}, {6,8}, {7,8}];

    edges := [seq(e, e in cbedg)];

    for e1 to nops(cbedg) do
        for e2 from e1+1 to nops(cbedg) do
            f1 := cbedg[e1]; f2 := cbedg[e2];

            if nops(f1 intersect f2) = 1 then
                edges :=
                [op(edges), {f1, f2}];
            fi;
        od;
    od;

    cind := 0;

    for perm in permute(3) do
        for flip in powerset(3) do
            sl :=
            [seq(q=pet_cube_symact(q, perm, flip),
                 q=1..8)];

            eperm := subs(sl, edges);

            cind := cind +
            pet_autom2cycles(edges, eperm);
        od;
    od;

    cind/48;
end;

Xedges :=
subs([seq(a[q]=n, q=1..36)], pet_cycleind_tcube_edges());
$\endgroup$
  • $\begingroup$ This is very nice though I don't understand much about group theory. Interestingly, the formula for truncated tetrahedron simplifies to $\frac{n^2(n^2+1)(n^2+2)(n^2+3)}{24}$ and for tetrahedron, it is $\frac{n^2(n^2+1)(n^2+2)(n^2+3)}{24}$. But for truncated cube, there isn't any similarity in the formula. Thank you very much for the help! $\endgroup$ – user352836 Jul 11 '16 at 0:41
  • $\begingroup$ Good observation. Note that the symmetric group produces ${n+3\choose 4}$ face colorings of an ordinary tetrahedron. Now the hexagonal and the triangular faces do not mix and every cycle of some length from $Z(S_4)$ produces two cycles of this length in the truncated tetrahedron, one for the triangles and another for the hexagons. Substituting $n$ into these squares of the original cycles we obtain ${n^2+3\choose 4}.$ $\endgroup$ – Marko Riedel Jul 11 '16 at 2:08
  • $\begingroup$ BTW we can think of the truncated tetrahedron as two nested tetrahedra (one each for the triangular faces and the hexagonal ones). These two have the same center. The second one is upside down, $\endgroup$ – Marko Riedel Jul 11 '16 at 18:15
  • $\begingroup$ That is a nice way to look at it! Thank you so much for the work you put in writing this wonderful answer. This was a great learning experience. :) $\endgroup$ – user352836 Jul 12 '16 at 5:18

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.