Projects

Final Project

  1. 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.

  2. 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

  1. One any one of the current graph theory conjectures
  2. On one of the DIMACS algorithm implementation challenges.
  3. Small-world phenomena in graphs
  4. Generalize and solve the electrical network problem with one bulb and k-toggle switches
  5. 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.
  6. Probabilistic graph theory: Erdős Rényi model.
  7. Probabilistic graph theory: Percolation Theory and Critical Phenomena
  8. Wiener’s phase transition for paraffin using the Wiener index.
  9. Explore some of the families of graphs counted by the Catalan numbers. Excerpt from Stanley’s combinatorics

Project Ideas from previous years class

  1. An introduction to matroids as an extension of graph theory.
  2. Embedding weighted graphs in \(\mathbf{R}^n\); multidimensional scaling and related algorithms.
  3. Ramsey Theory
  4. The Travelling Salesman Problem
  5. The spectrum of the Laplacian matrix; ``Can you hear the shape of a graph?’’
  6. An introduction to hypergraph theory as an extension of graph theory.
  7. Small-world networks
  8. An introduction to abelian sandpile models on directed graphs.
  9. Random walks on simple graphs.