SPEAKER: Johann Makowsky,
         Computer Science Department,
         Technion
<P>
TITLE:   On splitting formulas for graph polynomials

<P>


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.
<P>
What happens if those smaller matrices overlap just a bit?
<P>
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.
<P>
Our exposition is elementary and aimed at a wider audience.