2
$\begingroup$

graph

How many ways are there to color this graph with the following constraints? We have three colors: blue, red, green, and we require that the number of nodes of color green is 2, and blue 2, and red 2 - the same number.

And here is my attempt:

Automorphisms: $$(1)(2)(3)(4)(5)(6)$$ $$(34)(1)(2)(5)(6)$$ $$(56)(1)(2)(3)(4) $$ $$(34)(56)(1)(2)$$ $$(12)(35)(46)$$ $$(12)(36)(45)$$

Cycle index of group: $$Z_G(x_1,...,x_6) =\frac16 (x_1^6 + 2x_2^3 + 2x_2x_1^4 + x_2^2x_1^2) $$ And using Pólya theorem we get generating function: $$U_D(g,r,b) = Z_G(g+r+b, g^2+r^2+b^2, ...,g^6+r^6+b^6) = \\ \frac16 ((g+r+b)^6 + 2(g^2+r^2+b^2)^3 + 2(g^2+r^2+b^2)(g+r+b)^4 + (g^2+r^2+b^2)^2(g+r+b)^2)$$

And coefficient with $r^2g^2b^2$ is $\frac16 (90 + 12 +0 + 0 ) = 17$

Is it solution correct?

$\endgroup$
  • $\begingroup$ @markoriedel This looks like your department. $\endgroup$ – MJD Aug 28 '14 at 22:16
  • $\begingroup$ Okay, done, thanks. $\endgroup$ – Marko Riedel Aug 29 '14 at 21:31
1
$\begingroup$

I have little to add here, except maybe a verbal description of the automorphisms as they contribute to the cycle index $Z(G)$ of the automorphism group $G$. Let's do the enumeration one more time.

First, there is the identity, contributing $a_1^6$. There is a flip of the left fork, which gives $a_2 a_1^4.$ Same for the right fork, $a_2 a_1^4.$ With both forks flipped we get $a_1^2 a_2^2.$ Now do a flip about the vertical axis passing through the midpoint of the central bridge, yielding $a_2^3.$ Combine this flip with a single flip of one of the forks to get $2 a_2 a_4.$ Finally, there is the major flip combined with a flip of both forks for a contribution of $a_2^3.$

$$Z(G) = \frac{1}{8} (a_1^6 + 2 a_1^4 a_2 + a_1^2 a_2^2 + 2 a_2^3 + 2 a_2 a_4).$$

Doing the substitution we obtain $$Z(G)(R+B+G) = 1/8\, \left( R+B+G \right) ^{6}+1/4\, \left( R+B+G \right) ^{4} \left( {B}^{2}+{G}^{2}+{R}^{2} \right)\\ +1/8\, \left( R+B+G \right) ^{2} \left( {B}^{2}+{G}^{2}+{R}^{2} \right) ^{2}+1/4\, \left( {B}^{2}+{G}^{ 2}+{R}^{2} \right) ^{3}\\+1/4\, \left( {B}^{2}+{G}^{2}+{R}^{2} \right) \left( {B}^{4}+{G}^{4}+{R}^{4} \right).$$

This expands to $${B}^{6}+2\,{B}^{5}G+2\,{B}^{5}R+5\,{B}^{4}{G}^{2}+7\,{B}^{4}GR+5\,{B}^{ 4}{R}^{2}+5\,{B}^{3}{G}^{3}+12\,{B}^{3}{G}^{2}R\\+12\,{B}^{3}G{R}^{2}+5\, {B}^{3}{R}^{3}+5\,{B}^{2}{G}^{4}+12\,{B}^{2}{G}^{3}R+18\,{B}^{2}{G}^{2} {R}^{2}+12\,{B}^{2}G{R}^{3}\\+5\,{B}^{2}{R}^{4}+2\,B{G}^{5}+7\,B{G}^{4}R+ 12\,B{G}^{3}{R}^{2}+12\,B{G}^{2}{R}^{3}+7\,BG{R}^{4}+2\,B{R}^{5}\\+{G}^{6 }+2\,{G}^{5}R+5\,{G}^{4}{R}^{2}+5\,{G}^{3}{R}^{3}+5\,{G}^{2}{R}^{4}+2\, G{R}^{5}+{R}^{6}.$$

The result is that $$[R^2 G^2 B^2] Z(G) = 18.$$

This cycle index produces the following sequence when $N$ colors are used: $$1, 21, 171, 820, 2850, 8001, 19306, 41616, 82215, 151525,\ldots$$ which is $$\frac{1}{8} (N^6 + 2 N^5 + N^4 + 2 N^3 + 2 N^2).$$

The following Maple code was used to aid in this computation.

with(numtheory);
with(group):
with(combinat):


hgraph_cycleind := 
1/8*(a[1]^6 + 2*a[1]^4*a[2] + a[1]^2*a[2]^2 + 2*a[2]^3+ 2*a[2]*a[4] );

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;

v :=
proc(n)
        option remember;
        local p, k, gf;

        p := add(cat(q, k), k=1..n);
        gf := expand(pet_varinto_cind(p, hgraph_cycleind));

        subs({seq(cat(q, k)=1, k=1..n)}, gf);
end;

By way of a sanity check the coefficient on $R^5 G$ which is two seems correct, because there are only two colorings distinguished by whether the singleton ends up on a fork or on the bridge. Similarly the coefficient on $R^4 G^2$ is five, which corresponds to the two green elements on the same fork, on different forks, on the bridge, one on the bridge with the other on a fork one adjacent to it and one on the bridge with the other one on a fork not adjacent to it.

$\endgroup$
  • $\begingroup$ thanks you very much! But I don't see where you find $a_4a_2$ - could you show me it in cycle form ? $\endgroup$ – xawey Aug 29 '14 at 23:14

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.