Burnside's Lemma and coloring graph (first insight)
Months ago, while helping my junior working his skripsi, I learned about a theorem in algebraic combinatorics called Polya's Enumeration Theorem. Actually I already known this handy theorem before, but haven't give it much thought before.
Before explaining about Polya's Enumeration Theorem, it is cultural to explain first about Burnside Lemma, which is a theorem in a Group Theory..
As some of undergraduate student learn about permutation group. Denote $S_n$ as the permuation group of $n$ elements. It's particularly useful to think the $S_n$ as the set of all bijective functions $p:\{1,2,\cdots,n\} \rightarrow \{1,2,\cdots,n\}$.
Recall that any elements of $S_n$ can be represented by its cycle decomposition. For example in $S_8$, the function $p$ s.t $p(1)=1$, $p(2)=4$, $p(3)=2$, $p(4)=3 $, $p(5)=7$, $p(6)=5$, $p(7)=8$, $p(8)=6$ can be rewritten as $(1)(2 4 3)(5 7 8 6)$. In this case we say $f$ is decomposed into three cycles:
$(1)$ has length one
$(2 4 3)$ has length three
$(5 7 8 6)$ has length four.
Some books usually remove the cycle of length one, so then the permutations above are simply written as
$(2 4 3)(5 7 8 6)$, with no danger of confusion.
Orbit = Equivalence Class
Given a subgroup $D \subset S_n$, we define the relation $\sim_D$ on the set $\{1,2,\cdots, n\}$ as follow
$x \sim_D y$ if and only if there exists $p \in D$ such that $p(x)=y$.
It is easy to see that the above relation is an equivalence relation and so this relation partitions the set $\{1,2,\cdots, n\}$ into some disjoint classes by the rule of the subgroup $D$. We call these equivalence classes as the orbits of $D$ . When the notation comes into play , the orbit of $D$ which contains $x$ is usually denoted by $O_x$ and clearly since the identity function is always in the subgroup we have $O_x=\{p(x) | p \in D\}$.
Two elements $x$ and $y$ are contained in the same orbit of $D$ if and only if $x \sim_D y$ if and only if there exists $p \in D$ such that $p(x)=y$ if and only if by some rule of permutation in $D$, $x$ can be placed in the position that is previously occupied by $y$, and vice versa.
To count how many different orbits of $D$ are there we can use the following lemma, known as Burnside's Lemma
\[t=\frac{1}{|D|} \sum_{p \in D} F(p)\]
where $F(p)$ is the number of the fix points of permutation $p$.
Permuting The Graph
Suppose that the graph $G$ has $n$ vertices, each vertices are numbered by numbers from $1$ to $n$. Since for any $p \in S_n$, $p$ permutes $1,2, \cdots, n$ then $p$ also permutes the vertices of $G$ without changing its edging rule, that's the resulting graph is isomorphic to the permuted graph.
For example doing the permutation $(1 2 3)$ to a triangle graph (vertices are numbered 1,2, and 3 clockwise from the top ) is equivalent to rotating the triangle.
Coloring Graph
Suppose that we want to color a graph $n$ vertices $G$ , with the set of Color $V:=\{c_1,c_2, \cdots. c_m\}$. Each coloring can be uniquely represented by the function $c: \{1,2, \cdots, n\} \rightarrow V$, by mean that $c(k)=c_3$ means that the vertex with number $k$ is colored by $c_3$ color (one can specify $c_3$ as blue, red, white etc.). The function ruling the assignment of the colors into each vertex. The set of all functions $c: \{1,2, \cdots, n\} \rightarrow V$ is denoted by $C_{n,m}$.
Given a permutation $p \in S_n$, for any coloring function $c \in C_{n,m}$ consider the function $\bar{p}: C_{n,m} \rightarrow C_{n,m}$
\[\bar{p}(c) := c \circ p^{-1}\].
We can prove that $\bar{p}$ is a bijective from $C_{n,m}$ to itself.
What does the $\bar{p}$ actually mean?
As we already know that $p$ permutes the vertices of the graph. And after the graph has been colored, we know that permuting the vertices also permuting the color attached on each of it and hence resulting the other coloring, OR in other words resulting another element of $C_{n,m}$. For example $\bar{p}(c_1)=c_2$ means that the coloring $c_2$ is obtained by permuting the vertices of the graph which are already been colored by using coloring $c_1$, and the permutation used is permutation $p$.
The set $\bar{S_n}=\{\bar{p}: p \in S_n\}$ is a group. In fact, it consists the permutation of the color-function. That is we can view it as the permuation group $S_{|C_{n,m}|}$. It is easy to see that $|C(n,m)|=m^n$ and hence $|S_{|C_{n,m}|}|=(m^n)!$
Given a subgroup $H$, then we can define $\bar{H}=\{\bar{p}: p \in H\}$. It is not hard to prove that $\bar{H}$ is a subgroup of $\bar{S_n}$.
A question then arise:
What are the orbits of $\bar{H}$ in $S_{|C{m,n}|}$ ?
They should be the subsets of $C_{n,m}$. Observe that, two elements $c_1,c_2 \in C_{n,m}$ are in the same orbit of $\bar{H}$ if and only if there exists $\bar{p} \in \bar{H}$ such that $p(c_1)=c_2$.
That is any coloring contained in the same orbit of $\bar{H}$ is just the permutation of each other using permutation in $H$ (not necessarily $\bar{H}$).
For simplicity, let assume that $G=R_4$ is a rectangle and $V=\{red,blue,green\}$. In this case $R_4$ has four vertices denoted by the number $1,2,3$ and $4$, numbered clockwise starting from the top-left vertex (actually the rule of numbering isn't really a big deal, one can use different numbering for initial graph as long as he/she keep it consistent).
To make it shorter, we will refer a coloring as a string with four letters, where the $i$-th letter denote the initial of the color assigned to vertex $i$, that is the coloring $rbrg$is understood to br$c(1)=red$, $c(2)=blue$, $c(3)=red$ and $c(4)=green$.
Now, imagine an already colored rectangular graph as a rectangular toy. Then the toys obtained from the coloring $rbrg$, $grbr$, $rgrb$, and $brgr$ are the same toy, up to a rotation (several rotations $90^\circ$ clockwise by the center of rectangle). And the toys obtained from the coloring $rbrg$ and $brgr$ are also the same (obtained by flipping the toy).
Therefore to enumerate all different toys, we need to count the toy and its corresponded toys obtained by rotation or flip as one.
[for those who are not familiar with symmetric group]
In $R_4$, initially we have the numbered vertices in order 1-2-3-4. After rotating the graph 90 degree clockwise, the position previously occupied by 1 is now being occupied by 4, the 2's position is now being occupied by 1, the 3's position is now being occupied by 2, and the 4's position is now being occupied by 3. Therefore we have done the permutation $\rho(1)=4$, $\rho(2)=1$, $\rho(3)=2$, $\rho(4)=3$ or $(1 4 3 2)$. Similarly, the flip permutation is simply $(1 2)(3 4)$. And all possible combination of permutation of the $R_4$ obtained from flipping or rotating are contained in
\[\begin{align*}D_4 =\{& (1)(2)(3)(4), (1)(2 4)(3), (1 2)(3 4), (1 2 3 4), (1 3)(2)(4), \\ &(1 3)(2 4), (1 4 3 2), (1,4)(2,3)\}\end{align*}\]
that is our Dihedral Group.
[Don't Forget Our $\bar{H}$ ]
As, we already seen before, the orbits of $\bar{H}$ are the subsets of $C_{n,m}$. And two elements (colorings) $c_1,c_2 \in C_{n,m}$ are in the same orbit, if there exists $\overar{p} \in \bar{H}$ such that $\bar{p}(c_1)=c_2$.
Therefore, in the Toy Factory example, if we set $H=D_4$, we see that the Toys contained in the same orbit of $\bar{H}$ in $S_{|C_{n,m}|}$ are same. Thus the number of different orbits of $overbar{H}$ in $S_{|C_{n,m}|}$ is equal to the number of different Toys. The Burnside Lemma now becomes very handful.
In general, for any subgroup $H \subset S_n$, the number of different Orbits of $\bar{H}$ in $\bar{S_{n}}$ tells us the number of nonequivalent coloring of the $n$ vertices graph (up to subgroup $H$).
So then, how can we apply Burnside Lemma here? It should be
\[\frac{1}{|\bar{H}|} \sum_{ \bar{p} \in \bar{H} } F(\bar{p})\]
well, clearly $|\bar{H}|=|H|$, and also it doesn't really matter if we replace $\sum_{\bar{p} \in \bar{H}}$ with $\sum_{p \in H}$, since for each $p \in H$ we have $\bar{p} \in \bar{H}$ and vice-versa. Now it remains to find $F(\bar{p})$.
$F(\bar{p})$ counts how many elements of $C_{n,m}$ which is sent to itself by $\bar{p}$ (i.e the fixed-point of $\bar{p}$). That is how many $k$ such that $\bar{p}(f_k)=f_k$. Recall that $\bar{p}(f_k)= f_k \circ p^{-1}$, thus $\bar{p}(f_k)=f_k$ is equivalent to $f_k \circ p^{-1} = f_k$ and so $f_k = f_k \circ p$. If we set $p$ to be identity map $id_n$, then all $f_k \in C_{n,m}$ satisfy $f_k = f_k \circ p$, thus $F(\bar{id_n})= |C_{n,m}|=m^n$.
Consider the cycle composition of $p$, say
\[p=(a_{j_1} a_{j_1+1} \cdots a_{j_2 -1})(a_{j_2} \cdots a_{j_3 -1}) \cdots (a_{j_i} \cdots a_{j_{i+1}-1}) \cdots (a_{j_l} \cdots a_n)\]
that is $p$ is composed into $l$ cycles.
A routine calculation shows that $f_k = f_k \circ p$ implies
\[f_k(a_{j_1})=f_k(a_{j_1+1}) = \cdots = f_k(a_{j_2 -1}).\]
And similarly
\[f_k(a_{j_i })= f_k(a_{j_i + 1}) \cdots = f_k(a_{j_{i + 1}-1}).\]
An indication that the number of the cycles of $p$ is involved in the $F(\bar{p})$, so we denote it by $c(p)$, where in above $c(p)=l$. In fact, to determine $f_k$, we only need to know the value of $f_k(a_{j_i})$ for $i=1,2,\cdots,l$. So the number of such $f_k$ is equal to the number of function $f: \{a_{j_1}, \cdots, a_{j_l} \} \rightarrow \{c_1, c_2, \cdots, c_m\}$ which is easily computed to be $m^{l}$. Thus we have $F(\bar{p})= m^{c(p)}$. (it is consistent with our earlier observation when $p$ is identity map.)
And we get the formula for the number of nonequivalent colorings (up to symmetric group $H$) of graph $G$ with $n$ vertices is
\[\frac{1}{|H|} \sum_{p \in H} m^{c(p)}\]
where $m$ is the number of colors used and $c(p)$ is the number of cycles in the cycle decomposition of $p$.
The application of this theorem will be reviewed on the next post.
Before explaining about Polya's Enumeration Theorem, it is cultural to explain first about Burnside Lemma, which is a theorem in a Group Theory..
As some of undergraduate student learn about permutation group. Denote $S_n$ as the permuation group of $n$ elements. It's particularly useful to think the $S_n$ as the set of all bijective functions $p:\{1,2,\cdots,n\} \rightarrow \{1,2,\cdots,n\}$.
Recall that any elements of $S_n$ can be represented by its cycle decomposition. For example in $S_8$, the function $p$ s.t $p(1)=1$, $p(2)=4$, $p(3)=2$, $p(4)=3 $, $p(5)=7$, $p(6)=5$, $p(7)=8$, $p(8)=6$ can be rewritten as $(1)(2 4 3)(5 7 8 6)$. In this case we say $f$ is decomposed into three cycles:
$(1)$ has length one
$(2 4 3)$ has length three
$(5 7 8 6)$ has length four.
Some books usually remove the cycle of length one, so then the permutations above are simply written as
$(2 4 3)(5 7 8 6)$, with no danger of confusion.
Orbit = Equivalence Class
Given a subgroup $D \subset S_n$, we define the relation $\sim_D$ on the set $\{1,2,\cdots, n\}$ as follow
$x \sim_D y$ if and only if there exists $p \in D$ such that $p(x)=y$.
It is easy to see that the above relation is an equivalence relation and so this relation partitions the set $\{1,2,\cdots, n\}$ into some disjoint classes by the rule of the subgroup $D$. We call these equivalence classes as the orbits of $D$ . When the notation comes into play , the orbit of $D$ which contains $x$ is usually denoted by $O_x$ and clearly since the identity function is always in the subgroup we have $O_x=\{p(x) | p \in D\}$.
Two elements $x$ and $y$ are contained in the same orbit of $D$ if and only if $x \sim_D y$ if and only if there exists $p \in D$ such that $p(x)=y$ if and only if by some rule of permutation in $D$, $x$ can be placed in the position that is previously occupied by $y$, and vice versa.
To count how many different orbits of $D$ are there we can use the following lemma, known as Burnside's Lemma
\[t=\frac{1}{|D|} \sum_{p \in D} F(p)\]
where $F(p)$ is the number of the fix points of permutation $p$.
Permuting The Graph
Suppose that the graph $G$ has $n$ vertices, each vertices are numbered by numbers from $1$ to $n$. Since for any $p \in S_n$, $p$ permutes $1,2, \cdots, n$ then $p$ also permutes the vertices of $G$ without changing its edging rule, that's the resulting graph is isomorphic to the permuted graph.
For example doing the permutation $(1 2 3)$ to a triangle graph (vertices are numbered 1,2, and 3 clockwise from the top ) is equivalent to rotating the triangle.
Coloring Graph
Suppose that we want to color a graph $n$ vertices $G$ , with the set of Color $V:=\{c_1,c_2, \cdots. c_m\}$. Each coloring can be uniquely represented by the function $c: \{1,2, \cdots, n\} \rightarrow V$, by mean that $c(k)=c_3$ means that the vertex with number $k$ is colored by $c_3$ color (one can specify $c_3$ as blue, red, white etc.). The function ruling the assignment of the colors into each vertex. The set of all functions $c: \{1,2, \cdots, n\} \rightarrow V$ is denoted by $C_{n,m}$.
Given a permutation $p \in S_n$, for any coloring function $c \in C_{n,m}$ consider the function $\bar{p}: C_{n,m} \rightarrow C_{n,m}$
\[\bar{p}(c) := c \circ p^{-1}\].
We can prove that $\bar{p}$ is a bijective from $C_{n,m}$ to itself.
What does the $\bar{p}$ actually mean?
As we already know that $p$ permutes the vertices of the graph. And after the graph has been colored, we know that permuting the vertices also permuting the color attached on each of it and hence resulting the other coloring, OR in other words resulting another element of $C_{n,m}$. For example $\bar{p}(c_1)=c_2$ means that the coloring $c_2$ is obtained by permuting the vertices of the graph which are already been colored by using coloring $c_1$, and the permutation used is permutation $p$.
The set $\bar{S_n}=\{\bar{p}: p \in S_n\}$ is a group. In fact, it consists the permutation of the color-function. That is we can view it as the permuation group $S_{|C_{n,m}|}$. It is easy to see that $|C(n,m)|=m^n$ and hence $|S_{|C_{n,m}|}|=(m^n)!$
Given a subgroup $H$, then we can define $\bar{H}=\{\bar{p}: p \in H\}$. It is not hard to prove that $\bar{H}$ is a subgroup of $\bar{S_n}$.
A question then arise:
What are the orbits of $\bar{H}$ in $S_{|C{m,n}|}$ ?
They should be the subsets of $C_{n,m}$. Observe that, two elements $c_1,c_2 \in C_{n,m}$ are in the same orbit of $\bar{H}$ if and only if there exists $\bar{p} \in \bar{H}$ such that $p(c_1)=c_2$.
That is any coloring contained in the same orbit of $\bar{H}$ is just the permutation of each other using permutation in $H$ (not necessarily $\bar{H}$).
For simplicity, let assume that $G=R_4$ is a rectangle and $V=\{red,blue,green\}$. In this case $R_4$ has four vertices denoted by the number $1,2,3$ and $4$, numbered clockwise starting from the top-left vertex (actually the rule of numbering isn't really a big deal, one can use different numbering for initial graph as long as he/she keep it consistent).
To make it shorter, we will refer a coloring as a string with four letters, where the $i$-th letter denote the initial of the color assigned to vertex $i$, that is the coloring $rbrg$is understood to br$c(1)=red$, $c(2)=blue$, $c(3)=red$ and $c(4)=green$.
Now, imagine an already colored rectangular graph as a rectangular toy. Then the toys obtained from the coloring $rbrg$, $grbr$, $rgrb$, and $brgr$ are the same toy, up to a rotation (several rotations $90^\circ$ clockwise by the center of rectangle). And the toys obtained from the coloring $rbrg$ and $brgr$ are also the same (obtained by flipping the toy).
Therefore to enumerate all different toys, we need to count the toy and its corresponded toys obtained by rotation or flip as one.
[for those who are not familiar with symmetric group]
In $R_4$, initially we have the numbered vertices in order 1-2-3-4. After rotating the graph 90 degree clockwise, the position previously occupied by 1 is now being occupied by 4, the 2's position is now being occupied by 1, the 3's position is now being occupied by 2, and the 4's position is now being occupied by 3. Therefore we have done the permutation $\rho(1)=4$, $\rho(2)=1$, $\rho(3)=2$, $\rho(4)=3$ or $(1 4 3 2)$. Similarly, the flip permutation is simply $(1 2)(3 4)$. And all possible combination of permutation of the $R_4$ obtained from flipping or rotating are contained in
\[\begin{align*}D_4 =\{& (1)(2)(3)(4), (1)(2 4)(3), (1 2)(3 4), (1 2 3 4), (1 3)(2)(4), \\ &(1 3)(2 4), (1 4 3 2), (1,4)(2,3)\}\end{align*}\]
that is our Dihedral Group.
[Don't Forget Our $\bar{H}$ ]
As, we already seen before, the orbits of $\bar{H}$ are the subsets of $C_{n,m}$. And two elements (colorings) $c_1,c_2 \in C_{n,m}$ are in the same orbit, if there exists $\overar{p} \in \bar{H}$ such that $\bar{p}(c_1)=c_2$.
Therefore, in the Toy Factory example, if we set $H=D_4$, we see that the Toys contained in the same orbit of $\bar{H}$ in $S_{|C_{n,m}|}$ are same. Thus the number of different orbits of $overbar{H}$ in $S_{|C_{n,m}|}$ is equal to the number of different Toys. The Burnside Lemma now becomes very handful.
In general, for any subgroup $H \subset S_n$, the number of different Orbits of $\bar{H}$ in $\bar{S_{n}}$ tells us the number of nonequivalent coloring of the $n$ vertices graph (up to subgroup $H$).
So then, how can we apply Burnside Lemma here? It should be
\[\frac{1}{|\bar{H}|} \sum_{ \bar{p} \in \bar{H} } F(\bar{p})\]
well, clearly $|\bar{H}|=|H|$, and also it doesn't really matter if we replace $\sum_{\bar{p} \in \bar{H}}$ with $\sum_{p \in H}$, since for each $p \in H$ we have $\bar{p} \in \bar{H}$ and vice-versa. Now it remains to find $F(\bar{p})$.
$F(\bar{p})$ counts how many elements of $C_{n,m}$ which is sent to itself by $\bar{p}$ (i.e the fixed-point of $\bar{p}$). That is how many $k$ such that $\bar{p}(f_k)=f_k$. Recall that $\bar{p}(f_k)= f_k \circ p^{-1}$, thus $\bar{p}(f_k)=f_k$ is equivalent to $f_k \circ p^{-1} = f_k$ and so $f_k = f_k \circ p$. If we set $p$ to be identity map $id_n$, then all $f_k \in C_{n,m}$ satisfy $f_k = f_k \circ p$, thus $F(\bar{id_n})= |C_{n,m}|=m^n$.
Consider the cycle composition of $p$, say
\[p=(a_{j_1} a_{j_1+1} \cdots a_{j_2 -1})(a_{j_2} \cdots a_{j_3 -1}) \cdots (a_{j_i} \cdots a_{j_{i+1}-1}) \cdots (a_{j_l} \cdots a_n)\]
that is $p$ is composed into $l$ cycles.
A routine calculation shows that $f_k = f_k \circ p$ implies
\[f_k(a_{j_1})=f_k(a_{j_1+1}) = \cdots = f_k(a_{j_2 -1}).\]
And similarly
\[f_k(a_{j_i })= f_k(a_{j_i + 1}) \cdots = f_k(a_{j_{i + 1}-1}).\]
An indication that the number of the cycles of $p$ is involved in the $F(\bar{p})$, so we denote it by $c(p)$, where in above $c(p)=l$. In fact, to determine $f_k$, we only need to know the value of $f_k(a_{j_i})$ for $i=1,2,\cdots,l$. So the number of such $f_k$ is equal to the number of function $f: \{a_{j_1}, \cdots, a_{j_l} \} \rightarrow \{c_1, c_2, \cdots, c_m\}$ which is easily computed to be $m^{l}$. Thus we have $F(\bar{p})= m^{c(p)}$. (it is consistent with our earlier observation when $p$ is identity map.)
And we get the formula for the number of nonequivalent colorings (up to symmetric group $H$) of graph $G$ with $n$ vertices is
\[\frac{1}{|H|} \sum_{p \in H} m^{c(p)}\]
where $m$ is the number of colors used and $c(p)$ is the number of cycles in the cycle decomposition of $p$.
The application of this theorem will be reviewed on the next post.
Post a Comment: