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 logconcave, and hence unimodal.
The matching polynomial

All the roots of generating matching polynomial are real (HeilmannLieb).
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 logconcave.
 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. 1523.

The roots of the independence polynomial of clawfree 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 350357

The complex roots of the independence polynomial are dense.
But there are many graphs (not clawfree) 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 273282

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 , BaoXuan Zhu
European Journal of Combinatorics,
Volume 32, Issue 1, January 2011, Pages 1020
The project

Make a story from this material which you can lecture in 23 hours.
 Start with the matching polynomial.
 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.
 Discuss why this does not suffice for the independence polynomial to show
unimodality for all graphs. Note it suffcies for clawfree graphs.
 Explain the counterexample to unimodality for the independence polynomial.
 Discuss some further examples where unimodality holds.