Faculty of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel
Lecture 2: 2015/07/21 Tue 3:30PM-5:10PM
Lecture 3: 2015/07/22 Wed 3:30PM-5:10PM
Room: E6-1, Room 2412
We introduce the most prominent graph polynomials (characteristic, Laplacian, chromatic, matching, Tutte) and discuss how to compare them.
Lecture 2: Why is the Chromatic Polynomial a Polynomial?
We give an alternative proof for the fact that the chromatic polynomial is indeed a polynomial. From this we introduce generalized chromatic polynomials, and show that this actually represents the most general case; Every (reasonably defined) graph polynomial can be represented as a generalized chromatic polynomial.
Lecture 3: Hankel matrices and Graph Polynomials.
We introduce Hankel matrices of graph paramaters, which generalize Lovasz’ connection matrices. We show that many (but not all) graph polynomials have Hankel matrices of finite rank. We show how to use the Finite Rank Property to show definability/non-definability of graph parameters/polynomials in Monadic Second Order Logic.