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
-
Make a story from this material which you can lecture in 2-3 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 claw-free graphs.
- Explain the counterexample to unimodality for the independence polynomial.
- Discuss some further examples where unimodality holds.