Burnside Lemma and colorings of a $C_{8}$ graph

Question

I'm trying to determine the number of different colorings of the vertices of a cycle $C_{8}$ graph. Suppose I have 10 colors and I suppose I can use every color as much as I want. I consider two colorings to be the same if I can get from one to the other via an isometry of the octagon. How many different colorings are there?

I tried applying Burnside's lemma, but I'm not really getting anywhere. I know that the order of the symmetries of the graph is the order of the dihedral group $D_{8}$ so 16, but I don't really know how to apply the rest of the lemma. Help would be greatly appreciated!

Answer 1

By burnside's lemma, the number of orbits in the action (classes of unique colorings) is equal to:

$$\frac{\sum\limits_{g\in G}X_g}{|G|}$$.

Where $X_g$ is the number of colorings fixed by a given element $g$ of the group.

In $D_{8\times 2}$ there are $6$ "types" of elements, first are the $4$ reflexions that don't fix any element, then the $4$ reflexions that fix no vertices, the rotations of order $8$, $4$ and $2$, and last but not least the identity.

Notice the reflections that fix no vertices, fix $10^4$ colorings (because they split $C_8$ into $4$ pairs of vertices, such that each pair maps to itself under the action). So we add $4(10^4)$.

The reflections that fix two opposite vertices, fix $10^5$ colorings (because they split the vertices into $3$ pairs of vertices and two fixed vertices). So we add $4(10^5)$

The rotations of order $8$ fix $10$ colorings, every color must be of the same color. So we add $4(10)$.

The rotations of order $4$ fix $10^2$ colorings. So add $2(10^2)$ ( because the permutation splits the cycles into two orbits).

The rotation of order $2$ fixes $10^4$ colorings (it split the vertices into $4$ pairs).

The identity clearly fixes all $10^{8}$ permutations.

So by Burniside there are:

$$\frac{4(10^4)+ 4(10)^5 +4(10)+2(10)^2+10^4+10^{8}}{16}=6278140$$

unique colorings.

Answer 2

You will need to write out a classification of the isometries and find how many fixed points each has. I will do one for you and leave the rest up to you.

Consider the isometry which is a reflection in a line, where the line passes through two vertices of the octagon. Under this symmetry,

• two vertices are fixed: these vertices can have (independently) any colours you like;
• two vertices are mapped to each other: if the octagon is going to look the same after the transformation, these two must have the same colour;
• the same goes for two further pairs of vertices.

So, there are $10^5$ choices for the colouring which are fixed under this isometry. Moreover, there are $4$ isometries like this, so you have a subtotal of $4\times10^5$ fixed points.

See if you can do the rest. (Further hint: you can do all the remaining reflections in one hit, but you will have to consider $4$ cases for the rotations.)