Group Projects

Project 1: Domination and The Five Queens Problem

What is the smallest number of queens that we can place on a chessboard so that every space on the board is either occupied by a queen or being attacked by at least one queen? How can you use graph theory to find a suitable arrangement of queens on an nxn chessboard? To find a solution to this problem, you will learn about the dominating set of a graph.

Project 2: Unknotting knots

A knot invariant is an algorithm for assigning a number, polynomial, etc. to a knot which will be the same if two knots are the same. If the two knots are different the knot invariant will hopefully be different. In this project you will work toward defining an invariant which involves looking at a diagram of a knot and seeing how many crossing you have to change to get the unknot (a circle). Further directions could include finding classes of knots that your invariant helps distinguish. We will also briefly explore whether this invariant is useful in studying tangled DNA.

Project 3: Vertex Covers and River Crossings

Suppose a farmer wants to transport his wolf, goat, and cabbage across a river, but he only has one extra seat in his boat. Since the wolf wants to eat the goat and the goat wants to eat the cabbage, he can't leave the wolf and the goat or the goat and the cabbage alone. What is the best way to transport all three across the river? How can we understand this problem in terms of the vertex cover of a graph? If the problem becomes more complicated, how many seats does the farmer need in his boat for the problem to have a solution?

Project 4: Braid invariants

Any two knots which are the same can be related by a series of what are called Reidemeister moves. Every knot has what is called a braid representation. For this project, you will work on finding moves analogous to the Reidemeister moves, but which relate braid representations of the same knots.

Project 5: Eulerian Paths and The Seven Bridges of Konigsberg

The city of Konigsberg consisted of two sides of the Pregel River and two large islands, all connected to each other by seven bridges. Leonhard Euler invented graph theory in order to determine if one could walk across each of the bridges once and only once. For this project, you will learn about Eulerian paths to determine if this problem has a solution.

Project 6: Satellite knots

Given two knots, one can make what is called a satellite knot. For this project, your goal is to determine whether or not there is a unique way to express a knot as a satellite. In other words, can you find two sets of knots which are different, but give you the same knot when you satellite them? If not, why not?

Project 7: Kirchoff's Matrix-Tree Theorem

How can we associate a matrix to a graph? How many possible spanning trees does any given graph have? You will learn about the Laplacian matrix of a graph and its eigenvalues to see how to calculate the total number of spanning trees of a graph.

Project 8: The Jones polynomial and alternating knots

A knot can be drawn in the plane with a knot diagram. One simple knot invariant is the minimum number of crossings required in the diagram of knot. The Jones polynomial is a very interesting (and complicated) invariant of knots which assigns a (Laurent) polynomial to a knot. However, it turns out that there is a nice relationship between the crossing number and the Jones polynomial for a class of knots called alternating knots. The goal of this project will be to determine what this relationship is.