Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many ways can one paint the edges of a Petersen graph black or white?

I know that the symmetrygroup of the Petersen graph is $ [S5][1]$. Furthermore this this seems like a case where I should use Burnside's lemma. I'm sorry if the following is too verbose or uses non standard notation; I haven't been acquainted with graph theory.

S5 has 7 conjugacy classes, namely those with cycle types: (1,1,1,1,1),(1,1,1,2),(2,2,1),(2,3),(1,1,1,3),(4,1),(5). S5 has 15 edges so the identity (1,1,1,1,1) would leave $2^{15}$ different colorings fixed. The n-cycle (5) is a rotation of the whole graph and as such would leave $2^3$ colorings fixed. The "outside" could be white or black, the connecting edges and the "inside" edges could both be either white or black. Rotation around one "connecting" edge involves the (2,2,1) cycles. I won't tire you with the details but I found $2^9$ colorings.

From here I'm stuck however, I can't find any more symmetries than these. How do I find the colorings left fixed by the other conjugacy classes?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

I hope I can be of help here even if my approach is not the most sophisticated. I have written a Maple program to compute the action of the automorphism group $G$ of the Petersen graph on its edges (giving the edge permutation group $Q$), using properties that are documented at Wikipedia. My vertices are the number pairs that can be chosen from $\{1, 2, 3, 4, 5\}$. I used a brute force method going through all vertex permutations and checking that they preserve the property that two vertices are adjacent iff the two number pairs are disjoint, i.e. the Kneser graph property of the Petersen graph. That yields the automorphism group $G$ of the vertices. To conclude apply every permutation from $G$ to the edges, thereby obtaining $Q$ and its cycle index. At this point it remains to substitute $x+y$ into the cycle index according to Polya's theorem to obtain the generating function of the orbits. There are $396$ of them.

This is the cycle index: $$Z(Q) = {\frac {1}{120}}\,{a_{{1}}}^{15}+{\frac {5}{24}}\,{a_{{2}}}^{6}{a_{{1}}}^ {3}+1/6\,{a_{{3}}}^{5}+1/6\,a_{{3}}{a_{{6}}}^{2}+1/4\,{a_{{4}}}^{3}a_{{2} }a_{{1}}+1/5\,{a_{{5}}}^{3}.$$

Substituting $x+y$ into $Z(Q)$ yields $$Z(Q)_{x+y} = {\frac {1}{120}}\, \left( x+y \right) ^{15}+{\frac {5}{24}}\, \left( {x}^ {2}+{y}^{2} \right) ^{6} \left( x+y \right) ^{3}\\ +1/6\, \left( {x}^{3}+{y} ^{3} \right) ^{5}+1/6\, \left( {x}^{3}+{y}^{3} \right) \left( {x}^{6}+{y }^{6} \right) ^{2} \\ +1/4\, \left( {x}^{4}+{y}^{4} \right) ^{3} \left( {x}^{ 2}+{y}^{2} \right) \left( x+y \right) +1/5\, \left( {x}^{5}+{y}^{5} \right) ^{3}.$$

Expanding we find the generating function that classifies the edge colorings according to the two colors: $$Z(Q)_{x+y} = {x}^{15}+{x}^{14}y+3\,{x}^{13}{y}^{2}+9\,{x}^{12}{y}^{3}+19\,{x}^{11}{y}^ {4}+37\,{x}^{10}{y}^{5}+58\,{x}^{9}{y}^{6}+70\,{x}^{8}{y}^{7}\\ +70\,{x}^{7} {y}^{8}+58\,{x}^{6}{y}^{9}+37\,{x}^{5}{y}^{10}+19\,{x}^{4}{y}^{11}+9\,{x} ^{3}{y}^{12}+3\,{x}^{2}{y}^{13}+x{y}^{14}+{y}^{15}.$$

Setting $x=1$ and $y=1$ we find that the total count is equal to $$396.$$

The Maple program follows for all group theory enthusiasts who are also programmers! If there are any concrete questions as to what the individual functions do I will be happy to answer them. I can also resend the program if there are problems with the formatting. Enjoy! Comments are welcome.


with(group):
with(combinat):

pet_verts := convert(choose({seq(k, k=1..5)}, 2), list);

pet_edges_set := {};

for v1 in pet_verts do
    for v2 in pet_verts do
        if v1 intersect v2 = {} then
           pet_edges_set := pet_edges_set union {{v1, v2}};
        fi;        
    od;
od;

pet_edges := convert(pet_edges_set, list);

pet_is_autom :=
proc(vperm)
        local allsubs, e, eperm, el; 

        allsubs := 
        [seq(pet_verts[pos]=vperm[pos], pos=1..nops(vperm))];

        eperm := subs(allsubs, pet_edges);

        for e in eperm do
            el := convert(e, list);
            if el[1] intersect el[2] <> {} then
               return false;
            fi;            
        od;

        return true;
end;

pet_vautom := [];

pet_compute_vautom :=
proc()
        option remember;

        global pet_vautom;

        local vperm, pos, count;

        count := 0;
        for vperm in permute(pet_verts) do
            if pet_is_autom(vperm) then
               count := count+1; 
               printf("automorphism %d\n", count);

               pet_vautom := [op(pet_vautom), vperm];
            fi;
        od;

        pet_vautom;
end;
pet_compute_vautom();


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 := [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_vperm2eperm :=
proc(vperm)
        local allsubs, e, eperm, el; 

        allsubs := 
        [seq(pet_verts[pos]=vperm[pos], pos=1..nops(vperm))];

        return subs(allsubs, pet_edges);
end;

pet_cycleind := 
proc()
        local vperm, eperm, s;

        s := 0;

        for vperm in pet_vautom do
            eperm := pet_vperm2eperm(vperm);
            s := s + pet_autom2cycles(pet_edges, eperm);
        od;

        s/nops(pet_vautom);
end;

pet_varinto_cind :=
proc(poly, ind)
           local subs1, subs2, polyvars, indvars, v, pot, res;

           res := ind;

           polyvars := indets(poly);
           indvars := indets(ind);

           for v in indvars do
               pot := op(1, v);

               subs1 := 
               [seq(polyvars[k]=polyvars[k]^pot, 
               k=1..nops(polyvars))];

               subs2 := [v=subs(subs1, poly)];

               res := subs(subs2, res);
           od;

           res;
end;

pet_cycleind();
latex(%);

gf := pet_varinto_cind(x+y, pet_cycleind());

latex(gf);

latex(expand(gf));

subs({x=1, y=1}, gf);
share|improve this answer
    
Wow! Not exactly what I was looking for but very nicely done! –  Lee Wang Jan 21 '13 at 20:55
    
Here is another interesting computation using cycle indices. –  Marko Riedel Nov 10 '13 at 3:01

Using Burnside's lemma is the right idea.

Each element of $S_5$ determines a permutation of the 15 edges of the Petersen graph. If this permutation has exactly $r$ cycles on edges, then it fixes exactly $2^r$ 2-colorings of the edge set. If $a$ and $b$ are conjugate elements of $S_5$, then the permutations of the edges they determine have the same cycle structure. (To proof this, observe that the induced permutations are conjugate in $S_{15}$, and hence have the same cycle structure.)

So you just have to compute $r$ for one element in each conjugacy class, which is mildly tedious at worst, and then apply Burnside.

share|improve this answer
    
I'm not entirely sure if I follow your argument. How would one compute $r$ without a picture? My group theory book only deals with very simple visualizable cases. –  Lee Wang Jan 20 '13 at 20:39
    
An automorphism of Petersen is a permutation of its 10 vertices, and hence is an element of $S_{10}$. The set of all automorphisms forms a permutation group isomorphic to $S_5$, but not equal to it. You are dealing with a case where you cannot readily associate each automorphism with a picture, it is necessary to view each automorphism as a permutation. –  Chris Godsil Jan 20 '13 at 21:52
    
Ah that makes sense. But like I said my book only mentions cases where you can visualize the problem. I'm lost on how you would construct a nongeometric way to compte the $r$ for each conjugacy class. –  Lee Wang Jan 21 '13 at 20:55
1  
If $V(P)$ consists of pairs from $S=\{0,1,2,3,4\}$, then the edges correspond to partitions of $S$ with one cell of size 1 and two of size 2, e.g., $\{\{0\},\{1,2\},\{3,4\}\}$. Now the permutation $(01)(234)$ from $S_5$ maps this edge to $\{\{1\},\{0,3\},\{4,2\}\}$ and then to $\{\{0\},\{1,4\},\{2,3\}\}$ and so on. If we continue, we get a cycle of 6 edges. Choose an edge not in this cycle and repeat; eventually we arrange the 15 edges into cycles, and the number of these cycles is the value of $r$. Repeat for one permutation in each conjugacy class. –  Chris Godsil Jan 21 '13 at 22:15
    
Thank you very very much! This was truly helpful. –  Lee Wang Jan 22 '13 at 9:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.