Rutgers Discrete Mathematics Seminar

Title: Beyond Total Unimodularity

Speaker: Stefan van Zwam, Princeton University

Date: Tuesday, January 24th, 2012 2:10pm

Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ


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. In the late 90s, 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 addition I will sketch an extension of Kirchhoff's Matrix Tree Theorem to quaternionic unimodular matrices. That result is joint work with Rudi Pendavingh.