Line 13: | Line 13: | ||
== <u></u>'''Example 1: Square''' == | == <u></u>'''Example 1: Square''' == | ||
− | '''A basic example of how to use the | + | '''A basic example of how to use the theorems is a simple two-coloring of a square. <br>''' |
+ | |||
+ | '''Step 1: Look at all the different possible combinations of colorings:''' | ||
+ | |||
+ | |||
+ | |||
+ | {| width="200" border="1" cellspacing="1" cellpadding="1" | ||
+ | |- | ||
+ | | gggg | ||
+ | | gggr | ||
+ | | ggrg | ||
+ | | rggg | ||
+ | |- | ||
+ | | grgg | ||
+ | | ggrr | ||
+ | | rgrg | ||
+ | | rrgg | ||
+ | |- | ||
+ | | grrg | ||
+ | | rgrr | ||
+ | | grrr | ||
+ | | rrgr | ||
+ | |- | ||
+ | | rrrg | ||
+ | | rrrr | ||
+ | | grrg | ||
+ | | rggr | ||
+ | |} | ||
+ | |||
+ | |||
== '''Definitions:''' == | == '''Definitions:''' == | ||
Line 42: | Line 71: | ||
http://math.berkeley.edu/~mbaker/Tucker.pdf | http://math.berkeley.edu/~mbaker/Tucker.pdf | ||
− | http://www.whitman.edu/mathematics/SeniorProjectArchive/2012/Huisinga.pdf | + | http://www.whitman.edu/mathematics/SeniorProjectArchive/2012/Huisinga.pdf |
− | + | ||
+ | <br> | ||
<br> [[2014 Spring MA 375 Walther|Back to MA375 Spring 2014]] | <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:32, 20 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.
Example 1: Square
A basic example of how to use the theorems is a simple two-coloring of a square.
Step 1: Look at all the different possible combinations of colorings:
gggg | gggr | ggrg | rggg |
grgg | ggrr | rgrg | rrgg |
grrg | rgrr | grrr | rrgr |
rrrg | rrrr | grrg | rggr |
Definitions:
- Burnside
- Polya
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