$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 6.3: Burnside's Theorem

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Burnside's Theorem will allow us to count the orbits, that is, the different colorings, in a variety of problems. We first need some lemmas.

If $$c$$ is a coloring, $$[c]$$ is the orbit of $$c$$, that is, the equivalence class of $$c$$. Let $$G(c)$$ be the set of permutations in $$G$$ that fix $$c$$, that is, those $$\phi$$ such that $$\phi(c)=c$$; the permutation in figure 6.1.4 fixes the coloring in the bottom row, for example.

Lemma 6.2.1

$$G(c)$$ is a group of permutations.

Proof

We check the properties of a group from definition 6.1.1.

Suppose $$\phi$$ and $$\sigma$$ both fix $$c$$; then $$\phi(\sigma(c))=\phi(c)=c$$, so $$\phi\circ\sigma$$ fixes $$c$$ and $$\phi\circ\sigma\in G(c)$$.

The identity permutation fixes all colorings, so $$\id\in G(c)$$.

If $$\phi(c)=c$$ then $$\phi^{-1}(c)=\phi^{-1}(\phi(c))=\id(c)=c$$, so $$\phi^{-1}\in G(c)$$.

$$\square$$

Lemma 6.2.2

$$|G|=|[c]|\cdot|G(c)|$$.

Proof

For $$\phi$$ and $$\sigma$$ in $$G$$, define $$\phi\sim\sigma$$ if $$\sigma^{-1}\circ\phi\in G(c)$$. This is an equivalence relation:

1. $$\sigma^{-1}\circ\sigma$$ is the identity function, which is in $$G(c)$$. Thus $$\sigma\sim\sigma$$, so the relation is reflexive.
2. If $$\phi\sim\sigma$$, $$\sigma^{-1}\circ\phi\in G(c)$$. Then $$(\sigma^{-1}\circ\phi)^{-1}\in G(c)$$, and $$(\sigma^{-1}\circ\phi)^{-1}=\phi^{-1}\circ\sigma\in G(c)$$, so $$\sigma\sim\phi$$ and $$\sim$$ is symmetric.
3. If $$\phi\sim\sigma$$ and $$\sigma\sim\tau$$, then $$\sigma^{-1}\circ\phi\in G(c)$$ and $$\tau^{-1}\circ\sigma\in G(c)$$, so $$(\tau^{-1}\circ\sigma)\circ(\sigma^{-1}\circ\phi)\in G(c)$$. Since $$(\tau^{-1}\circ\sigma)\circ(\sigma^{-1}\circ\phi)= \tau^{-1}\circ\phi$$, $$\phi\sim\tau$$, and $$\sim$$ is transitive.

Now we claim that the equivalence class of $$\phi$$ is $$A=\{\phi\circ\sigma\mid\sigma\in G(c)\}$$. First, suppose that $$\sigma\in G(c)$$; then $$\phi^{-1}\circ\phi\circ\sigma=\sigma\in G(c)$$, so $$\phi\circ\sigma\sim\phi$$ and $$A\subseteq[\phi]$$. Next, suppose $$\phi\sim\tau$$, so $$\tau^{-1}\circ\phi=\gamma\in G(c)$$. Then $$\phi\circ\gamma^{-1}=\tau$$, so $$\tau\in A$$ and $$[\phi]\subseteq A$$.

Now we show that each equivalence class is the same size as $$G(c)$$. Define $$f\colon G(c)\to \{\phi\circ\sigma\mid\sigma\in G(c)\}$$ by $$f(\gamma)=\phi\circ\gamma$$. If $$f(\gamma_1)=f(\gamma_2)$$, then \eqalign{ \phi\circ\gamma_1&=\phi\circ\gamma_2\cr \phi^{-1}\circ\phi\circ\gamma_1&=\phi^{-1}\circ\phi\circ\gamma_2\cr \gamma_1&=\gamma_2\cr } so $$f$$ is 1–1. Since every $$\phi\circ\gamma\in\{\phi\circ\sigma\mid\sigma\in G(c)\}$$ is $$f(\gamma)$$, $$f$$ is onto.

Thus the number of equivalence classes is $$|G|/|G(c)|$$.

Finally, we show that the number of equivalence classes is $$|[c]|$$. Let the set of equivalence classes in $$G$$ be $$E$$, that is, $$E=\{[\phi]\mid \phi\in G\}$$. We define $$g\colon [c]\to E$$ and show that $$g$$ is a bijection. Suppose $$d\in[c]$$, so $$d=\sigma(c)$$ for some $$\sigma\in G$$. Let $$g(d)=[\sigma]$$.

First, we show $$g$$ is well-defined. If $$d=\sigma_1(c)=\sigma_2(c)$$, then $$\sigma_2^{-1}\circ\sigma_1(c)=c$$, so $$\sigma_1\sim\sigma_2$$ and $$[\sigma_1]=[\sigma_1]$$, that is, $$g(\sigma_1)=g(\sigma_2)$$.

Next, suppose $$g(d_1)=g(d_2)$$. This means that $$d_1=\sigma_1(c)$$, $$d_2=\sigma_2(c)$$, and $$[\sigma_1]=[\sigma_2]$$. Hence $$\sigma_2^{-1}\circ\sigma_1(c)=c$$, so $$\sigma_1(c)=\sigma_2(c)$$ and thus $$d_1=d_2$$, so $$g$$ is 1–1.

Suppose that $$[\sigma]\in E$$. Then $$g(\sigma(c))=[\sigma]$$, so $$g$$ is onto.

Thus we have $$|[c]|=|E|={|G|\over|G(c)|}$$ and $$|G(c)|\cdot|[c]|=|G|$$ as desired.

$$\square$$

Corollary 6.2.3

If $$c\sim d$$ then $$|G(c)|=|G(d)|$$.

Proof

Since $$c\sim d$$, $$[c]=[d]$$, and \eqalign{ {|G|\over|G(c)|} = |[c]|&=|[d]|= {|G|\over|G(c)|}\cr |G(c)|&=|G(d)|\cr }\] $$\square$$ Definition 6.2.4 If group $$G$$ acts on the colorings of an object and $$\sigma\in G$$, $$\fix(\sigma)$$ is the set of colorings that are fixed by $$\sigma$$. Theorem 6.2.5 (Burnside's Theorem) If group $$G$$ acts on the colorings of an object, the number of distinct colorings modulo $$G$$ is{1\over|G|}\sum_{\sigma\in G} |\fix(\sigma)|.\]

Proof

Let $$C$$ be the set of all colorings, and let $$\cal O$$ be the set of orbits. Let $$c_1,c_2,\ldots,c_k$$ be a list of colorings, one in each orbit, so that the orbits are $$[c_1],[c_2],\ldots,[c_k]$$. Consider the sum \ds\sum_{c\in C}|G(c)|: \eqalign{ \sum_{c\in C}|G(c)|&=\sum_{i=1}^k\sum_{c\in[c_i]}|G(c)|\cr &=\sum_{i=1}^k\sum_{c\in[c_i]}|G(c_i)|\cr &=\sum_{i=1}^k\sum_{c\in[c_i]}{|G|\over|[c_i]|}\cr &=\sum_{i=1}^k |[c_i]|{|G|\over|[c_i]|}\cr &=\sum_{i=1}^k |G|=|G|\sum_{i=1}^k 1 = |G||{\cal O}|.\cr } Then |{\cal O}| = {1\over|G|}\sum_{c\in C}|G(c)|. This already gives an interesting formula for \(|{\cal O}|, but it is unwieldy, since the number of colorings is typically quite large; indeed, since we typically want to compute the number of orbits for $$k$$ colors, the number of colorings is not a fixed number.

With just a little more work we can fix this problem: \eqalign{ \sum_{c\in C}|G(c)|&=\sum_{c\in C}\sum_{\sigma\in G(c)} 1\cr &=\sum_{\sigma\in G}\sum_{c\in \fix(\sigma)} 1\cr &=\sum_{\sigma\in G}|\fix(\sigma)|.\cr } Now $$|{\cal O}| = {1\over|G|}\sum_{\sigma\in G}|\fix(\sigma)|$$ as desired.

$$\square$$

Since the group of permutations in a typical problem is fairly small, the sum in Burnside's Theorem is usually manageable. Moreover, we can make the task of computing $$|\fix(\sigma)|$$ fairly straightforward. Let's consider a particular example, the permutation of figure 6.1.4, shown again in figure 6.2.1. If we are using $$k$$ colors, how many colorings of the pentagon are fixed by this permutation? Since the permutation swaps vertices 2 and 5, they must be the same color if $$\phi$$ is to fix the coloring. Likewise vertices 3 and 4 must be the same color; vertex 1 can be any color. Thus, the number of colorings fixed by $$\phi$$ is $$k^3$$. It is easy to see that every "flip'' permutation of the pentagon is essentially the same, so for each of the five flip permutations, the size of $$\fix(\sigma)$$ is $$k^3$$.

Figure 6.2.1. The cycles in a vertex permutation.

Every permutation can be written in cycle form: The permutation in figure 6.2.1, for example, is $$(1)(2,5)(3,4)$$. A cycle in this context is a sequence $$(x_1,x_2,\ldots,x_k)$$, meaning that $$\phi(x_1)=x_2$$, $$\phi(x_2)=x_3)$$, and so on until $$\phi(x_k)=x_1$$. Following our reasoning above, the vertices in each cycle must be colored the same color, and the total number of colors fixed by $$\phi$$ is $$k^m$$, where $$m$$ is the number of cycles.

Let's apply this to another permutation, shown in figure 6.2.2. This permutation consists of a single cycle, so every vertex must have the same color, and the number of colorings fixed by $$\phi$$ is $$k^1$$. All rotations of the pentagon consist of a single cycle except the trivial rotation, that is, the identity permutation. In cycle form, the identity permutation is $$(1)(2)(3)(4)(5)$$, so the number of colorings fixed by the identity is $$k^5$$. Putting everything together, we thus have $$|{\cal O}|={1\over 10}(k^5+k+k+k+k+k^3+k^3+k^3+k^3+k^3)= {1\over 10}(k^5+5k^3+4k).$$ For example, the number of different 3-colorings is $$(3^5+5\cdot3^3+4\cdot 3)/10=39$$.

Figure 6.2.2. The permutation $$(1,3,5,2,4)$$ is a single cycle.

Example 6.2.6 We find the number of distinct colorings of the vertices of a square with $$k$$ colors, modulo $$D_4$$, the dihedral group of size 8. The elements of $$D_4$$ are the four rotations $$r_0$$, $$r_{90}$$, $$r_{180}$$, $$r_{270}$$, where $$r_i$$ is the counterclockwise rotation by $$i$$ degrees, and the four reflections $$f_H$$, $$f_V$$, $$f_D$$, $$f_A$$, as indicated in figure 6.2.3.

Figure 6.2.3. The reflection axes for $$f_H$$, $$f_V$$, $$f_D$$, and $$f_A$$.

In cycle notation these permutations are: \eqalign{ r_0&=(1)(2)(3)(4)\cr r_{90}&=(1,4,3,2)\cr r_{180}&=(1,3)(2,4)\cr r_{270}&=(1,2,3,4)\cr f_H&=(1,4)(2,3)\cr f_V&=(1,2)(3,4)\cr f_D&=(1)(2,4)(3)\cr f_A&=(1,3)(2)(4).\cr } so the number of colorings is $$f(k)={1\over 8}(k^4+k+k^2+k+k^2+k^2+k^3+k^3)={1\over8}(k^4+2k^3+3k^2+2k).$$ For example, $$f(2)=6$$; the six colorings are shown in figure 6.2.4.

Figure 6.2.4. The six 2-colorings of the square.

Example 6.2.7 Here is a more complicated example: how many different graphs are there on four vertices? In this case, of course, "different'' means "non-isomorphic''. We can interpret this as a coloring problem: Color the edges of the complete graph $$K_4$$ with two colors, say black and white. The black edges form a graph; the white edges are the ones left out of the graph. The group $$G$$ we need to consider is all permutations of the six edges of $$K_4$$ induced by a permutation of the vertices, so $$|G|=4!=24$$. All we need to know is the number of cycles in each permutation; we consider a number of cases.

Case 1. The identity permutation on the vertices induces the identity permutation on the edges, with 6 cycles, so the contribution to the sum is $$2^6$$.

Case 2. A 4-cycle on the vertices induces a permutation of the edges consisting of one 4-cycle and one 2-cycle, that is, two cycles. There are $$3!=6$$ 4-cycles on the vertices, so the contribution of all of these is $$6\cdot2^2$$.

Case 3. A permutation of the vertices consisting of a 3-cycle and a 1-cycle induces a permutation of the edges consisting of two 3-cycles. There are $$4\cdot2=8$$ such permutations of the vertices, so the contribution of all is $$8\cdot2^2$$.

Case 4. A permutation of the vertices consisting of two 2-cycles induces a permutation of the edges consisting of two 1-cycles and two 2-cycles. There are $${1\over2}{4\choose2}=3$$ such permutations, so the contribution is $$3\cdot 2^4$$.

Case 5. A permutation of the vertices consisting of a 2-cycle and two 1-cycles induces a permutation of the edges consisting of two 1-cycles and two 2-cycles. There are $${4\choose2}=6$$ such permutations, so the contribution is $$6\cdot 2^4$$.

The number of distinct colorings, that is, the number of distinct graphs on four vertices, is

${1\over24}(2^6+6\cdot2^2+8\cdot2^2+3\cdot 2^4+6\cdot2^4)= {1\over24}(264)=11.$

It is possible, though a bit difficult, to see that for $$n$$ vertices the result is

\eqalignno{ f(n)&=\sum_{\bf j}\prod_{k=1}^n{1\over k^{j_k} j_k!} \prod_{k=1}^{\lfloor n/2\rfloor}2^{k j_{2k}} \!\!\prod_{k=1}^{\lfloor (n-1)/2\rfloor}\!\!2^{kj_{2k+1}} \prod_{k=1}^{\lfloor n/2\rfloor} 2^{kC(j_k,2)} \!\!\!\!\prod_{1\le r< s\le n-1}\!\!\!\!\!\!\!\! 2^{\gcd(r,s)j_rj_s}\qquad (6.2.1)\cr}

where the sum is over all partitions $${\bf j}=(j_1,j_2,\ldots,j_n)$$ of $$n$$, that is, over all $$\bf j$$ such that $$j_1+2j_2+3j_3+\cdots+nj_n=n$$, and $$C(m,2)={m\choose2}$$. With this formula and a computer it is easy to compute the number of graphs when $$n$$ is not too large; for example, $$f(5)=34$$, so there are 34 different five-vertex graphs.

In light of the forgoing discussion, we can restate theorem 6.2.5. If $$\sigma$$ is a permutation, let $$\#\sigma$$ denote the number of cycles when $$\sigma$$ is written in cycle form.

Corollary 6.2.8 If group $$G$$ acts on the colorings of an object, the number of distinct colorings modulo $$G$$ with $$k$$ colors is {1\over|G|}\sum_{\sigma\in G} k^{\#\sigma}.\]