SPEAKER: Johann Makowsky, Computer Science Department, Technion

TITLE: On splitting formulas for graph polynomials

ABSTRACT: The determinant and the permanent are special cases of multivariate polynomials with combinatorial interpretations. Computing the determinant of a matrix whose non zero entries all lie in disjoint matrices on the diagonal is done by taking the product of determinants of those matrices. The same holds for the permanent.

What happens if those smaller matrices overlap just a bit?

We discuss this problem, generalize it to a wide class of graph polynomials and state a general new theorem, the splitting theorem. It applies to the colored Tutte polynomial, Farrell polynomials, and various matching and rook polynomials.

Our exposition is elementary and aimed at a wider audience.