Projects
Final Project
-
Report. Should contain at least 5 pages and at most about 10 pages. It can be of the following two types:
a. Describe an area or problem in graph theory (or a closely related field), some interesting questions and results in the field, and should contain at least one proof. It could be a sketch of a proof if the proof is too complicated (like the 4 color theorem).
b. Provide full proofs of a related set of theorems that were not provided in class. Ex: All the directed versions of the theorems proved in class: matrix tree theorem, the Eulerian circuit theorem, etc.
-
Presentation: 10 minute powerpoint presentation of your project. This will be during exam week.
Coding can be a part of your project. Include a link to your code in your report.
Project Ideas
- One any one of the current graph theory conjectures
- On one of the DIMACS algorithm implementation challenges.
- Small-world phenomena in graphs
- Generalize and solve the electrical network problem with one bulb and k-toggle switches
- Provide (reasonable) generalizations of rock-paper-scissors. Don’t know if this will be able to produce enough material for a project, but it seems like a fun question to answer. Might be too simple.
- Probabilistic graph theory: Erdős Rényi model.
- Probabilistic graph theory: Percolation Theory and Critical Phenomena
- Wiener’s phase transition for paraffin using the Wiener index.
- Explore some of the families of graphs counted by the Catalan numbers. Excerpt from Stanley’s combinatorics
Project Ideas from previous years class
- An introduction to matroids as an extension of graph theory.
- Embedding weighted graphs in \(\mathbf{R}^n\); multidimensional scaling and related algorithms.
- Ramsey Theory
- The Travelling Salesman Problem
- The spectrum of the Laplacian matrix; ``Can you hear the shape of a graph?’’
- An introduction to hypergraph theory as an extension of graph theory.
- Small-world networks
- An introduction to abelian sandpile models on directed graphs.
- Random walks on simple graphs.