# Burnside's Lemma, applications

A relation $\sim$ on $C$ is equivalence if it is:

• reflexive: $c\sim c$ for all colorings $c$ belonging to $C$
• symmetric: $c_1\sim c_2$ implies $c_2\sim c_1$
• transitive: $c_1\sim c_2$ and $c_2\sim c_3$ implies $c_1\sim c_3$

A set of objects $S$, a set of colorings of these objects $C$ and a group of permutations $G$ representing symmetries possessed by configurations of the objects. Two colorings in $C$ are equivalent if there is a permutation in $G$ that transforms a coloring into the other.

Show that $\sim$ is an equivalence relation on $C$. How do you prove that?

As well as that, prove that $G_c$ is a subgroup of $G$.

-

It’s pretty straightforward; everything follows from the definition of group of permutations.

• Reflexivity: Since $G$ is a group, it contains the identity permutation, which transforms any coloring into itself.

• Symmetry: If there is a permutation $g\in G$ transforming a coloring $c_1$ into $c_2$, the inverse permutation $g^{-1}$, which must be in $G$, transforms $c_2$ to $c_1$.

• Transitivity: If there are permutations $g,h\in G$ transforming $c_1$ to $c_2$ and $c_2$ to $c_3$, respectively, they their group product $hg$, which necessarily belongs to $G$, transforms $c_1$ to $c_3$: it’s just a composition of functions.

-

You have a group $G$ (here the symmetric group of permutations) acting on a set $C$. The relation in question is defined as $c_1\sim c_2\iff \exists g\in G\colon c_1=gc_2$. Such is always an equivalence relation because $G$ is a group (neutral element gives reflexivity, inverse gives symmetry, the group operation gives transitivity). Remark: The equivalence classes in such a case are called orbits of an element under the group action.

If $c\in C$ we call $G_c:=\{g\in G\mid gc=c\}$ the stabilizer or fixgroup of $c$. It is a group because the neutral element fixes $c$, the inverse of $g$ fixes $c$ if $g$ fixes $c$ and if both $g_1$ and $g_2$ fix $c$ then so does theit composition $g_1g_2$.

-
How would you do the second part? proof that Gc is a subgroup of G. –  Max Nov 15 '12 at 18:49
@Max $Gc$ is not a soubgroup of $G$, it is an orbit withn $C$, isn't it? –  Hagen von Eitzen Nov 15 '12 at 18:51
gyazo.com/c6d513e5e79bcccbb2d1056cf0420abe this is all I've found that might shed a light on the situation.. –  Max Nov 15 '12 at 18:54
Oh, then why don't you write $G_c$ instead of $Gc$? What they write there as $\bar c$ is what I denoted $Gc$ - the orbit of $c$, whereas $G_c$ is the stabilizer. –  Hagen von Eitzen Nov 15 '12 at 18:55
A subgroup you mean? and if it was to make it more mathematical, would there be a way? –  Max Nov 15 '12 at 19:00