Unimodality of graph polynomials

Unimodality of graph polynomials

Guide lines for a project

A nice exposition of Newton's Theorem Newton's Real Root Theorem : If a polynomial has strictly positive real coefficients and all its roots are real, then it is log-concave, and hence unimodal.

The matching polynomial

The independence polynomial

The project

  1. Make a story from this material which you can lecture in 2-3 hours.
  2. Start with the matching polynomial.
  3. Use a lemma which states that if P(A) is a property of subsets of edges (vertices) which is closed under subsets, then the coefficients of the generating function of P(A) has strictly positive integer coefficients.
  4. Discuss why this does not suffice for the independence polynomial to show unimodality for all graphs. Note it suffcies for claw-free graphs.
  5. Explain the counterexample to unimodality for the independence polynomial.
  6. Discuss some further examples where unimodality holds.