User Tools

Site Tools


Stefan van Zwam (Princeton)

Beyond Total Unimodularity

Abstract for the Combinatorics Seminar 2013 March 12

A matrix is totally unimodular if the determinant of each square submatrix is in {-1, 0, 1}. A matroid is regular if it has a totally unimodular representation matrix. Such matroids are a cornerstone of the theory of integer programming. The deepest result on regular matroids 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 regular matroids, 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.

seminars/comb/abstract.201303zwa.txt · Last modified: 2020/01/29 14:03 (external edit)