Some Recursively Defined Graph Polynomials

- Wednesday
- The polynomial J (state, generating, and linear recursion forms)
- The polynomial j (state, generating, and linear recursion forms)
- Homework:
- Compute several small examples
- Find formula for J and j of blossoms
- Wednesday
- The polynomial P
- The Martin Polynomials (Give translation identities)
- Prove anticircuit counting and some zeros
- Homework:
- Compute several small examples
- Prove that J is an evaluation of P
- Friday
- Show x + y identity
- Homework:
- Prove x + y identity in oriented case
- (open problem) Find an analogous polynomial to P for the oriented case
- (open) Show that P is complete on (some classes) of graphs
- (open) Find combinatorial interpretations for other evaluations of P
- (open) Generalize P, J and j to matroids
- Week 2: The Tutte Polynomial
- Monday
- Show both rank-generating form and deletion contraction form
- Prove oriented Martin is an evaluation of Tutte for planar graphs
- Homework:
- Compute Tutte poly both ways of a simple graph
- Prove T(1,1) and T(-1,-1)
- Find formulas for T(tree), T(n-gon)
- Wednesday
- Prove Chromatic poly is an evaluation of Tutte
- Prove rank-generating and del/con are equivalent
- Homework:
- Use deletion and contraction to prove that Chromatic poly counts number of colorings
- Modify x + y proof to get Tutte’s identity, and give a description of what is going on
- Friday
- Applications of the Tutte polynomial
- Week 3: Relating Tutte and Martin, and the Penrose Polynomial
- Monday
- Wednesday
- Friday