1
$\begingroup$

I'm fairly new to group theory, and here's one problem I'm trying to solve:

We're coloring nodes of tetrahedron in 3 distinct colors, and its edges in 2 distinct colors. We're treating two colorings $c_1, c_2$ of the tetrahedron as equal, if we can rotate tetrahedron colored using $c_1$ to achieve $c_2$. (The rotations are in $\Bbb{R}^3$).

How many of such colorings are there?

I really have no idea how to do it. I heard it's somehow connected to Burnside's lemma, but for me it's a collection of abstract definitions that I can't see how to apply in this concrete example. How to think about such problems?

$\endgroup$
  • 2
    $\begingroup$ Look up Polya Enumeration. It is directly related to Burnside's lemma. The wiki page doesn't do a great job of defining everything, but if you read through an example you can probably figure out what everything is. $\endgroup$ – KidA424 Jun 13 '15 at 22:23
  • 1
    $\begingroup$ Try googling Burnside's Lemma or searching for answers on this site that apply it to counting problems. I've written a couple, but can't write out a full hint/toy example now. $\endgroup$ – Mark S. Jun 13 '15 at 22:31
2
$\begingroup$

I would treat this using Burnside. Using the variables $a$ for the vertices and $b$ for the edges, we have three types of rotations for a total of twelve. We compute their cycle structure and how many assignments they fix.

First type: identity, cycle structure $$a_1^4 b_1^6,$$ fixes $$3^4\times 2^6$$ colorings.

Second type: $180$ degree rotations about an axis passing through midpoints of opposite edges, cycle structure $$3\times a_2^2 b_1^2 b_2^2,$$ fixes $$3\times 3^2 \times 2^2 \times 2^2$$ colorings.

Third type: rotations by $120$ degrees and $240$ degrees about an axis passing through the center of a face to the opposite vertex, cycle structure $$4\times 2\times a_1 a_3 b_3^2,$$ fixes $$4\times 2\times 3 \times 3 \times 2^2$$ colorings.

Average over $12$ permutations by Burnside is $$\frac{1}{12} (5184 +432 + 288) = 492.$$

There is an extensive list of Polya / Burnside computations by various users at MSE meta.

Remark. The space of possible configurations is within reach of total enumeration. The following Maple program does this and the result of the computation is $$492.$$


v :=
proc()
    option remember;
    local res, orbit, vind, eind, vcol, ecol,
    cols, vperms, vperm, edges, eperms, eperm,
    q, v1, v2, p;

    vperms :=
    [[1,2,3,4], # identity
     [2,1,4,3], # 180 degree rotations
     [3,4,1,2],
     [4,3,2,1],
     [2,3,1,4], # 120/240 degree rotations
     [3,1,2,4],
     [1,3,4,2],
     [1,4,2,3],
     [3,2,4,1],
     [4,2,1,3],
     [2,4,3,1],
     [4,1,3,2]];

    edges := table(); q := 1;

    for v1 to 4 do
        for v2 from v1+1 to 4 do
            edges[{v1, v2}] := q;
            q := q+1;
        od;
    od;


    eperms := [];

    for vperm in vperms do
        eperm := [];

        for v1 to 4 do
            for v2 from v1+1 to 4 do
                eperm :=
                [op(eperm),
                 edges[{vperm[v1], vperm[v2]}]];
            od;
        od;

        eperms := [op(eperms), eperm];
    od;


    res := {};

    for vind from 3^4 to 2*3^4-1 do
        vcol := convert(vind, base, 3);

        for eind from 2^6 to 2*2^6-1 do
            ecol := convert(eind, base, 2);

            orbit := {};

            for p to 12 do
                cols := [seq(vcol[vperms[p][q]], q=1..4)];
                cols :=
                [op(cols),
                 seq(ecol[eperms[p][q]], q=1..6)];

                orbit := orbit union {cols};
            od;

            res := res union {orbit};
        od;
    od;


    nops(res);
end;

There is a variation on this that may be slightly easier to read.


v :=
proc()
    option remember;
    local res, orbit, vind, eind, vcol, ecol,
    cols, vperms, vperm, edges, eperms, eperm,
    q, v1, v2, p;

    vperms :=
    [[1,2,3,4], # identity
     [2,1,4,3], # 180 degree rotations
     [3,4,1,2],
     [4,3,2,1],
     [2,3,1,4], # 120/240 degree rotations
     [3,1,2,4],
     [1,3,4,2],
     [1,4,2,3],
     [3,2,4,1],
     [4,2,1,3],
     [2,4,3,1],
     [4,1,3,2]];

    edges := table();

    edges[{1,2}] := 1;
    edges[{1,3}] := 2;
    edges[{1,4}] := 3;
    edges[{2,3}] := 4;
    edges[{2,4}] := 5;
    edges[{3,4}] := 6;


    eperms := [];

    for vperm in vperms do
        eperm := [];

        for v1 to 4 do
            for v2 from v1+1 to 4 do
                eperm :=
                [op(eperm),
                 edges[{vperm[v1], vperm[v2]}]];
            od;
        od;

        eperms := [op(eperms), eperm];
    od;


    res := {};

    for vind from 3^4 to 2*3^4-1 do
        vcol := convert(vind, base, 3);

        for eind from 2^6 to 2*2^6-1 do
            ecol := convert(eind, base, 2);

            orbit := {};

            for p to 12 do
                cols := [seq(vcol[vperms[p][q]], q=1..4)];
                cols :=
                [op(cols),
                 seq(ecol[eperms[p][q]], q=1..6)];

                orbit := orbit union {cols};
            od;

            res := res union {orbit};
        od;
    od;


    nops(res);
end;
$\endgroup$

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.