- Task:
- Learn a new theorem about a numerical graph invariant and communicate it in written form.
- Minimum requirements:
- Each student will focus on a different numerical graph invariant.
- The written document will introduce, correctly state, and prove a theorem. It will also include at least one interesting example illustrating the theorem. The article will be as self-contained as possible. The new document must be typed, be at most eight pages in length (with one inch margins and a 12pt font), and be available in PDF format.
- Assessment and deadlines:
- Project grades will be computed as follows:
due date element weight 2012-10-10 outline 10% 2012-11-07 rough draft 20% 2012-11-14 feedback 20% 2012-11-28 final paper 50%
- Advice:
- Here are some suggestions on how to present mathematics: Halmos on writing and Kleiman on writing.
- Comments:
- By design, this assignment is very open-ended. Students are strongly
encouraged to compute many examples. Students are also encouraged to
formulate, test, and prove their own conjectures. Here are some questions
that you may want to consider:
- Can your numerical graph invariant be calculated for any graph, or does it only apply to certain graphs?
- Can you bound your numerical invariant?
- Can you describe the set of graphs with a given numerical invariant?
- How is the numerical invariant of a graph related to its subgraphs or minors?
- Is your notion of your numerical invariant particularly well-adapted for some application?
- Potential topics:
- The following numerical graph invariants (or simple formula involving
them) are natural candidates:
- algebraic connectivity — Hooman Alikhanian,
- arboricity — Dinushi Munasinghe,
- average path length — Meghan Laverty,
- Betti numbers,
- bipartite dimension,
- boxicity — Jessica O'Brien,
- branchwidth — Janelle Petrusma,
- chromatic index — Chris Price,
- clique number — Heather Maltby,
- Colin de Verdière's invariant,
- conductance — Ramiro Zurkowski,
- crossing number — Mary Robotham,
- cycle rank,
- degeneracy,
- diameter — Shayne Sharkey,
- dimension,
- distance,
- domatic number — Sylvie Smets,
- domination number — Azadeh Eftekhari,
- edge-connectivity,
- edge covering number,
- Estrada index,
- genus,
- girth — Chelsea Thompson,
- Hamiltonian paths — Zachary O'Keefe,
- Hosoya index,
- independence number,
- independent domination number,
- maximum betweenness,
- maximum closeness,
- maximum resistance distance,
- metric dimension,
- order of automorphism group,
- Parry-Sullivan invariant,
- pathwidth — Angie Hwang,
- Perron number,
- Ramsey numbers — Heather Maltby,
- rank,
- Randić index,
- Shannon capacity,
- spectrum — Seyed Mirsadeghi,
- Strahler number — Alex Mansourati,
- strength,
- toughness,
- Thue number — Fraser Carey,
- variance of vertex degrees,
- vertex-connectivity — Kristen Chen,
- vertex cover number,
- Wiener index.