| Line 11: | Line 11: | ||
<br> | <br> | ||
| − | == '''A basic explanation''' == | + | == '''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. | ||
| + | <br> | ||
| − | 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 x<sup>n </sup><sup></sup>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 2<sup>4 </sup><sup></sup><sup></sup>=16 colorings. We show this in the picture below: | + | 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 x<sup>n </sup><sup></sup>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 2<sup>4 </sup><sup></sup><sup></sup>=16 colorings. We show this in the picture below: |
| − | <br> fg 1[[Image:TwoColoringCombinations.jpg|left|800x600px|All possible two coloring combinations of a 2x2 square.]] | + | <br> fg 1[[Image:TwoColoringCombinations.jpg|left|800x600px|All possible two coloring combinations of a 2x2 square.]] |
| − | <div><br></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div>Now with these coloring we can see that some are actually equivalent, or isomorphic, to each other by just turning the square as seen below:</div><div>fg 2[[Image:TwoColoringCombinations2.jpg|400x300px|Isomorphisms of a 2x2 square.]] </div><div>If we do this then we can plainly see that there are 6 unique colorings.</div> | + | <div><br></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div></div><div>Now with these coloring we can see that some are actually equivalent, or isomorphic, to each other by just turning the square as seen below:</div><div>fg 2[[Image:TwoColoringCombinations2.jpg|400x300px|Isomorphisms of a 2x2 square.]] </div><div>If we do this then we can plainly see that there are 6 unique colorings.</div> |
fg 3[[Image:TwoColoringCombinations3.2.jpg|400x300px|Six unique two colorings of a 2x2 square.]] | fg 3[[Image:TwoColoringCombinations3.2.jpg|400x300px|Six unique two colorings of a 2x2 square.]] | ||
<div><div> | <div><div> | ||
| − | 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 | + | 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 |
| − | + | ||
| + | <br> | ||
| − | 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. | + | 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. |
[[Image:EightPossibleOrbits.jpg|450x600px]] | [[Image:EightPossibleOrbits.jpg|450x600px]] | ||
| − | 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: | + | 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: |
| − | + | ||
| + | <br> | ||
At this point we will look at the last column. The values of x<sub>p</sub><sup>n </sup><sup></sup>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). | At this point we will look at the last column. The values of x<sub>p</sub><sup>n </sup><sup></sup>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 x<sub>4</sub><sup>1</sup><sub></sub>''. ''Another example is (1)(3)(24) for an r-orbit. There are two 1-cycles and one 2-cycle so it is represented as x<sub>1</sub>''<sup>''2''</sup>''x<sub>2</sub><sup>1</sup>.'' | + | ''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 x<sub>4</sub><sup>1</sup><sub></sub>''. ''Another example is (1)(3)(24) for an r-orbit. There are two 1-cycles and one 2-cycle so it is represented as x<sub>1</sub>''<sup>''2''</sup>''x<sub>2</sub><sup>1</sup>.'' Now here comes the real magic of this chart. If we take the sum of column 4 then we get the following equation: |
| − | Now here comes the real magic of this chart. If we take the sum of column 4 then we get | + | |
| + | |||
| + | |||
| + | Then if we take the number of orbits in G; |G|=8 and divide the equation by that then we get the Burnside equation for our square. A quick check will show how many unique colorings exist. Plug 2( the number of colors) into the equation for all x<sub>p </sub><sub></sub>and you will get 6 which is what we found earlier! | ||
| + | |||
| + | |||
| + | |||
| + | So what was described above was the basic approach to Burnside. We did it for a simple square but the process is just as easily done for a cube. The following link will take you to a chart for a cube and the equation for it. | ||
<br> '''Definitions:''' | <br> '''Definitions:''' | ||
| Line 68: | Line 75: | ||
<br> | <br> | ||
| − | + | <br> [[2014 Spring MA 375 Walther|Back to MA375 Spring 2014]] </div> </div> | |
| − | <br> [[2014 Spring MA 375 Walther|Back to MA375 Spring 2014]] | + | [[Category:MA375Spring2014Walther]] [[Category:Math]] [[Category:Project]] |
| − | [[Category:MA375Spring2014Walther]] [[Category:Math]] [[Category:Project]] | + | |
| − | + | ||
| − | + | ||
Revision as of 12:56, 24 April 2014
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 the following equation:
Then if we take the number of orbits in G; |G|=8 and divide the equation by that then we get the Burnside equation for our square. A quick check will show how many unique colorings exist. Plug 2( the number of colors) into the equation for all xp and you will get 6 which is what we found earlier!
So what was described above was the basic approach to Burnside. We did it for a simple square but the process is just as easily done for a cube. The following link will take you to a chart for a cube and the equation for it.
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
