Document Type
Lecture
Publication Date
12-3-2008
Abstract
A matrix over Q is totally unimodular if every square submatrix has determinant 0, 1, or −1. Totally unimodular matrices are of fundamental importance in integer linear programming. A precise characterization of such matrices was given by Seymour (1980) in a paper titled Decomposition of Regular Matroids. Roughly speaking, such matrices are built from the incidence matrices of graphs, their ”transposes”, and an exceptional matrix by three types of summing operations. A matrix over Q is dyadic if every square submatrix has determinant in {0, ±2i|i ∈ Z}. Whittle conjectured that a similar decomposition theorem holds for dyadic matrices, where the basic building blocks are the incidence matrices of signed graphs, their ”transposes”, and a finite number of exceptional matrices. In this talk, we will give a short survey of Seymour’s result and show recent progress on Whittle’s conjecture by Qin, Slilaty and Zhou.
Relational Format
presentation
Recommended Citation
Zhou, Xianqian, "Signed Graphs and Their Matroids" (2008). Combinatorics Seminar. 86.
https://egrove.olemiss.edu/math_combinatorics/86
