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 rbrgis understood to brc(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 rbrgis understood to brc(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: