Combinatorics -- Projects
Projects
The final project for this course involves giving a talk on a topic related to Combinatorics. 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 May 17 and 19.
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:
- April 28: 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.)
- May 17 and 19: Presentations occur.
Possible Topics
Here are some possible topics. If you have ideas for other topics, come talk to me. When you decide on a topic, let me know as soon as possible (each group needs to have a different topic, and I'll cross out topics as I learn who is doing which topic). Your topic needs to be a topic that you don't already know, so make sure to choose a topic that you haven't seen in a different class.
- Graph Theory: Graph Theory is a fairly large subject, but we will only spend a few days of class on it. Here are some possible topics from graph theory:
- Eulerian Trails and Hamiltonian Cycles — See Chapter 9 of our Combinatorics textbook.
- Minimum Weight Spanning Tree — See Section 10.2 of our Combinatorics textbook.
Matchings in Graphs — See Sections 11.3 and 11.5 of our Combinatorics textbook.
Planar Graphs — See Chapter 12 of the textbook.
- Chromatic Polynomial — See me for the book Introduction to Graph Theory by Robin Wilson (chromatic polynomial is covered in Section 5.3 of Edition 5 and Section 21 of Edition 4).
- Network Flows and Max Flow/Min Cut — See me for the book Introduction to Graph Theory by Robin Wilson (Network Flows are in Section 6.3 of Edition 5 and Section 29 of Edition 4).
- Maximum Weight Matchings — See me for the book Introduction to Operations Research by Hillier and Lieberman (Maximum Weight Matchings are in Sections 8.3 and 8.4 of this book).
Matroids — Matroids are a generalization of both graphs and matrices.
See the paper Matroids You Have Known by David L. Neel and Nancy Ann Neudauer.
Combinatorial Games: Combinatorial Games are a fun part of combinatorics, which we unfortunately did not have time to cover in this course. Here are some possible topics:
Other Topics: