2
$\begingroup$

Let's look at a graph consisting of 6 vertices(enumerated by 1 to 6) which has the following symmetry group $G = \langle id, (12),(34),(13)(24)(56)\rangle \leq S_6$. Stupid question first: this group has only 4 elements, right? The cycle index(https://en.wikipedia.org/wiki/Cycle_index) of $G$ is $Z_G = 1/4(x_1^6+2 x_1^4 x_2 + x_2^3)$, correct? Now, I want to count the number of different colourings of this graph with two colours where two colourings are the same if they lie in the same orbit under the action of $G$. To apply Polya's theorem (https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem) I take as generating function for the colours $1+x$. Then Polya's theorem, as I understand it, tells me that the generating function of all possible colourings equals $Z_G(1+x,1+x^2,...) = 1/4((1+x)^6+2(1+x)^4(1+x^2)+(1+x^2)^3)$-

1) Is it correct, that to get the total number of possible colourings, one just plucks in $Z_G(2,2,...)$? This would give here 34.

2) Of course, one could also ask for all possible colourings where a certain number ($l$) of vertices is blue and the rest is red, i.e., for the coefficient of $x^l$ in $Z_G$. Is there a smart way in general to get this coeffient, other than just multiplying out everything which seems cumbersome?

$\endgroup$
0
$\begingroup$

You're in luck: My high-school final year project was on exactly this matter. I also implemented the general procedure in Python code back then, and it's all booted up and ready to tackle your problem. As for the general methodology however, I can already say that you are correct in (1), i.e. you do substitute 2 for all variables in the cycle index if you intend to use 2 colors. But with one remark: you don't make any "color-polynomial"-related substitutions if you want all colorings whatsoever, you directly insert the number of colors into the cycle index as-is.

As for (2), the most general tip I can give you is that you can use the multinomial theorem (a more general version of the binomial theorem) and some crossing-off of irrelevant terms to easen the burden when manually computing. (Here you do substitute the arguments for the "color polynomials" though)

Now, let's tackle that example of yours to have a practice run at (2). First off, it seems that your group is a bit bigger than you believe. I have a Python-function which generates the following group from your given generating set (interpret the following as permutations, written in table-form but with the top row in sorted order and omitted, I will clean it up asap):

$\{[4, 3, 2, 1, 6, 5], [3, 4, 2, 1, 6, 5], [4, 3, 1, 2, 6, 5], [2, 1, 3, 4, 5, 6], [1, 2, 4, 3, 5, 6], [2, 1, 4, 3, 5, 6], [1, 2, 3, 4, 5, 6], [3, 4, 1, 2, 6, 5]\}$

Anyhow, the cycle index turns out to be

$$Z_G(x_1,x_2,x_4)=\frac{1}{8} ( 2x_2x_4 + x_1^2x_2^2 + x_1^6 + 2x_1^4x_2 + 2x_2^3 )$$

And the answer to (1) is $\frac{1}{8} ( 2\cdot 2\cdot 2 + 2^2\cdot2^2 + 2^6 + 2\cdot 2^4\cdot 2 + 2\cdot 2^3 )=21$

As for (2), we substitute for each $x_i$ the polynomial $(b^i+w^i)$ ($b$ for black, $w$ for white). When considering $k$ colors, replace each $x_i$ with $\sum_{n=1}^k c_n^i$.

We get the polynomial:

$$\frac{1}{8} \Big( 2(b^2+w^2)(b^4+w^4) + (b+w)^2(b^2+w^2)^2 + (b+w)^6 + 2(b+w)^4(b^2+w^2) + 2(b^2+w^2)^3 \Big)$$

Let's say we want the number of symmetrically inequivalent colorings where 3 vertices are black and 3 are white, i.e. we want the coefficient of the $b^3w^3$-term. Clearly we cannot obtain any such terms from $2(b^2+w^2)(b^4+w^4)$ or $2(b^2+w^2)^3$, so we can just ignore those. We have the following remaining polynomial after crossing off those terms:

$$\frac{1}{8} \Big( (b+w)^2(b^2+w^2)^2 + (b+w)^6 + 2(b+w)^4(b^2+w^2) \Big)$$

We tackle each term one by one:

  • $(b+w)^2(b^2+w^2)^2$: We can only take one $b^2$ and one $w^2$ from the factor $(b^2+w^2)^2$. 2 ways to do so. After that, we have 2 ways to choose one $b$ and one $w$ from $(b+w)^2$ to fill up the exponents. Total contribution: $2^2=4$.
  • $(b+w)^6$: Use the binomial theorem: $\binom{6}{3}=20$.
  • $2(b+w)^4(b^2+w^2)$: We choose either of the terms in $(b^2+w^2)$, and then choose one of the same color from $(b+w)^4$, and take three of the other color from what remains. Contribution: $2\cdot 4\cdot 2=16$

Now, sum up, and don't forget to divide by the order of the group: $\frac{4+20+16}{8}=5$ ways.

I hope some of the main tricks shone through in the example.

$\endgroup$
  • $\begingroup$ Thanks. I see, it needs some practice to apply it :-) Maybe you know any good sources of examples to practice? $\endgroup$ – Mekanik Dec 9 '15 at 16:24
  • $\begingroup$ Well…I did play around a lot with my Python code…and my project report (in english, code included) is published on the web, so I could always hand over the url to it. As for generating a subgroup from a generating set, I have no specific sources to give, but you can easily construct your own examples in small groups such as $S_6, S_5, S_4$ and $S_3$, and work those out without too much effort. As for computing cycle indices and working out the number of colorings, I learned the stuff partly from my supervisors and partly from the book Discrete Mathematics by Norman L. Biggs. $\endgroup$ – A.Sh Dec 9 '15 at 16:33
  • $\begingroup$ I suppose it is worth mentioning that there are mathematical software such as Maple / Mathematica that have some built-in methods for generating groups from generating sets, and cycle indices. Just in case you have such software available...but I'm not too familiar with those two...Also, yes, it took me quite a lot of practice to make this problem as routine as it is today, a couple years later :) $\endgroup$ – A.Sh Dec 9 '15 at 16:38

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.