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

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?

-

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 perm, vperm, pos, count;

count := 0; perm := firstperm(nops(pet_verts));

while type(perm, list) do
vperm :=
[seq(pet_verts[perm[q]], q=1..nops(pet_verts))];

if pet_is_autom(vperm) then
count := count+1;
printf("automorphism %d\n", count);

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

perm := nextperm(perm);
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_petersen_edges :=
proc()
option remember;
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_petersen_edges();
latex(%);

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

latex(gf);

latex(expand(gf));

subs({x=1, y=1}, gf);


Addendum Mar 24 2016. A much improved solution to this problem is at the following MSE link which renders the above obsolete.

-
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.

-
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
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