Beyond Total Unimodularity

-
Stefan van Zwam, Princeton University
Fine Hall 224

A matrix is TOTALLY UNIMODULAR if the determinant of each square submatrix is in {-1, 0, 1}. Such matrices are a cornerstone of the theory of integer programming. The deepest result on such matrices is Seymour's decomposition theorem. The only known way to test efficiently whether a matrix is totally unimodular makes use of this theorem. Recently, Whittle introduced several classes of matrices with similar properties: the determinants of the submatrices are restricted to a certain set. In this talk I will discuss some results from the theory of totally unimodular matrices from the point of view of matroid theory, and outline which of those results will, won't, or might generalize to Whittle's classes. In particular I will sketch an extension of Kirchhoff's matrix tree theorem to quaternionic unimodular matrices. That result is joint work with Rudi Pendavingh.