We discuss in class colorings of graphs, where adjacent vertices have different colors. Suppose you took the graph to be a polygon and allowed the graph to be reflected and rotated. How many different colorings do you get?
Contents
Outline/Title?
Introduction
In graph theory, it is sometimes necessary to find the number of ways to color the vertices of a polygon. Two theorems that work together to solve this problem are the Polya theorem and Burnside theorem.
A basic explanation
To begin, we will begin with a simple 2 colored 2x2 square and eventually I will explain how to apply it for an n-colored 2x2 and a cube. From there the reader should have a basic understanding so that they could apply on n-colored n-gons.
In order to find the total possible ways to color a 2x2 square with 2 colors, we take the number of colors and multiply it by itself for the total number of points. Giving the formula xn where x is the number of colors and n is the number of points. For this example we will use x=2 and n=2x2=4. Thus 24 =16 colorings. We show this in the picture below:
fg 1
fg 3
This is simple for a 2-coloring of an 2x2 square but to have a more scientific approach and to verify that our answer is correct then we have to use Burnside's Theorem
The best way to show this is with a fairly complicated table. First we need to understand the notation shown in column 2. The picture below shows what each letter means.
These reflections and rotation are the the elements of the group G, we will call these the orbits. What is important is the number of orbits that are within G but we wil get to that in a little while. Now the next step is to take each of the orbits and apply them to the 16 original colorings and see which of the colorings are fixed, meaning that none of the verticies change color. Doing this will give you column 3. The number values is just the number of coloring that do not move for each line. Now let's take a look at the chart:
At this point we will look at the last column. The values of xpn are going to be used for the final equation of burnside and eventually for Polya. The value for p is the length it takes to get around the longest cycle while n is the number of individual cycles ( the green numbers).
For example if we take (1234) as cycle for the square. There is only one cycle and it takes 4 applications to get around, i.e. if you start at 1, you go to 2, then 3, then 4, and back to 1. This would be represented by x41. Another example is (1)(3)(24) for an r-orbit. There are two 1-cycles and one 2-cycle so it is represented as x12x21. Now here comes the real magic of this chart. If we take the sum of column 4 then we get
Definitions:
- Burnside-The lemma counts the number of orbits of a set X acted upon by a group G. # of Orbits = (1/|G|) Sum over G |x^g|. Where x^g is an element of x such that g(x) = x, and |x^G| is the number of elements that fit this defintion.
- Polya-Applies this to colors.
'
'Formula:
- show formula
- breakdown of each element
- relate back to example 1
Proof:
References and Additional Information
For further reading on the Polya theorem:
http://arxiv.org/pdf/1001.0072.pdf
http://math.berkeley.edu/~mbaker/Tucker.pdf
http://www.whitman.edu/mathematics/SeniorProjectArchive/2012/Huisinga.pdf
Back to MA375 Spring 2014
