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: Planar Graphs, Euler's Formula, and Brussels Sprouts A graph is called planar if it can be drawn without any of its edges crossing. For this project, you will learn about Euler's formula for planar graphs, which relates the number of vertices, edges, and faces of a graph in one equation. You will also learn about a paper-and-pen game called "Brussels sprouts." Can you use Euler's formula to ensure that you win the game every time? 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.