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:
1. Compute several small examples
2. 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:
1. Compute several small examples
2. Prove that J is an evaluation of P
• Friday
• Show x + y identity
• Homework:
1. Prove x + y identity in oriented case
2. (open problem) Find an analogous polynomial to P for the oriented case
3. (open) Show that P is complete on (some classes) of graphs
4. (open) Find combinatorial interpretations for other evaluations of P
5. (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:
1. Compute Tutte poly both ways of a simple graph
2. Prove T(1,1) and T(-1,-1)
3. 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:
1. Use deletion and contraction to prove that Chromatic poly counts number of colorings
2. 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