Projects

The final project for this course involves giving a talk on a topic related to Graph Theory. You can work in groups of 2 or 3 people, or you can work by yourself. Here is some basic information:

• The talk should be about 5 minutes + 5 minutes/person (for example, one person should give a 10 minute talk, and two people should give a 15 minute talk).
• The talk must use computer slides (such as PowerPoint or Beamer).

The presentations will occur on Dec. 15 and 17.

Your talk should focus on explaining the main ideas of your topic clearly, so that the audience (the other members of the class) can understand it. For some of the topics listed below, there is too much material to present in the given time — in that case, you should choose some part of the material to present.

Deadlines:

• December 3: Tell me which topic you are doing, and who is in your group. (Each group needs to choose a different topic, so that all of the presentations are different.)
• Dec. 15 and 17: Presentations occur.

Possible Topics

Here are some possible topics. Each topic suggests one reference. In addition to the suggested reference, I recommend looking up additional information on the topic in another book or online. If you have ideas for other topics, come talk to me.

• Stable Matchings: See Section 9.3 of the book Introductory Combinatorics by Brualdi (you can get this book from me). This year's Nobel Prize in Economics went to Shapley and Roth people for their work on Stable Matchings.
• The Shannon Switching Game: See Section 11.6 in Introductory Combinatorics by Brualdi (you can get this book from me). This is a game played on a graph where one player tries to create a path between two specified vertices, while another player tries to remove edges to prevent the first player from succeeding.
• Polytopes: See Discrete and Computational Geometry by Devadoss and O'Rourke (you can get this book from me). We have talked some about polytopes in class but there are many more things one can ask — Why are there only five Platonic polyhedra in 3-dimensions? What are the regular polytopes in higher dimesions? Could a polyhedron be flexible (while maintaining its edge lengths)?
• Ramsey Theory: See Section 8.3 of Introduction to Graph Theory by West, which is available in the library (or from me if the library copy is checked out). Ramsey Theory generalizes the dinner party problem from the first day of class
• Random Graphs: See Section 8.5 of Introduction to Graph Theory by West, which is available in the library (or from me if the library copy is checked out). A random graph on n vertices is created by randomly deciding whether each possible edge is in the graph or not.
• Proof of the Classification of Surfaces: See Appendix C of Shape of Space by Weeks, which is available in the library. In class, we learned that all surfaces are either a connected sum of tori or projective planes, but we did not prove this fact. This book provides a nice proof of this fact.
• The Game of Sprouts: See Graph Theory and the Game of Sprouts by Mark Copper. This is a game where players take turns adding an edge and a vertex to a graph in a specified way. In addition to reading the above paper, I recommend trying to determine if there is an optimal strategy that allows the first player (or second player) to win if the game begins with 2 vertices or 3 vertices?
• Minimum Weight Matchings: If you have a weighted bipartite graph, you may want to find a matching with minimum weight. This problem is called the Assignment Problem and an algorithm to solve it is the Hungarian Algorithm. See Sections 8.3 and 8.4 of Introduction to Operations Research by Hillier and Lieberman (you can get this book from me).
• Voronoi Diagram: See Voronoi Diagrams by Aurenhammer and Klein. Consider a set of n points in the plane. The Voronoi diagram of this set of points partitions the plane into n regions, with each region corresponding to a point. The region corresponding to a given point is all points in the plane that are closer to that point than to the other points.
• Ridigity of Bar Frameworks: A bar framework is a graph in the plane (or in 3-dimensions) where the vertices are free to move around as long as the lengths of the edges remain constant. See pages 74–75 of Edition 5 of the textbook and also see the book Counting on Frameworks by Graver (you can get this book from me).
• The Art Gallery Problem: See Chapter 35 of Proofs from THE BOOK by Aigner and Ziegler (you can get this book from me). This is about determining the minimum number of guards needed to guard an art gallery so that together they can observe the whole art gallery.