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.