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

• All the roots of generating matching polynomial are real (Heilmann-Lieb).
For a proof see the Lecture Notes by I. Averbouch from my 2007 Lectures on The characteristic and matching polynomial.
• Show that the generating matching polynomial is log-concave.
• Can you apply the same argument for the defect matching polynomial?

## The independence polynomial

• The independence polynomial is NOT unimodal. For a proof, see the paper : of
Y. Alavi, P. Malde, A. Schenk and P. Erdos,
The vertex Independence Sequence of a graph is not constrained,
Congressus Numerantium 58 (1987) pp. 15-23.
• The roots of the independence polynomial of claw-free graphs are all real. See the paper : The roots of the independence polynomial of a clawfree graph,
Maria Chudnovsky and Paul Seymour,
Journal of Combinatorial Theory, Series B
Volume 97, Issue 3, May 2007, Pages 350-357
• The complex roots of the independence polynomial are dense. But there are many graphs (not claw-free) such that the independence polynomial has only real roots.
See the paper : On the Location of Roots of Independence Polynomials
J.I. Brown, C.A. Hickman, R.J. Nowakowski
Journal of Algebraic Combinatorics, May 2004, Volume 19, Issue 3, pp 273-282
• Survey on the independence polynomial by Vadim E. Levit and Eugen Mandrescu from 2005.
• A more recent paper from 2011 is:
On the unimodality of independence polynomials of some graphs
Yi Wang , Bao-Xuan Zhu
European Journal of Combinatorics, Volume 32, Issue 1, January 2011, Pages 10-20

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